The k-assignment problem (or, the k-matching problem) on k-partite graphs is an NP-hard problem for $k\ge 3$. In this paper we introduce five new heuristics. Two algorithms, ${\mathrm{B}}_m$ and ${\mathrm{C}}_m$, arise as natural improvements of Algorithm ${\mathrm{A}}_m$ from (He et al., in: Graph Algorithms And Applications 2, World Scientific, 2004). The other three algorithms, ${\mathrm{D}}_m$, ${\mathrm{E}}_m$, and ${\mathrm{F}}_m$, incorporate randomization. Algorithm ${\mathrm{D}}_m$ can be considered as a greedy version of ${\mathrm{B}}_m$, whereas ${\mathrm{E}}_m$ and ${\mathrm{F}}_m$ are versions of local search algorithm, specialized for the k-matching problem. The algorithms are implemented in Python and are run on three datasets. On the datasets available, all the algorithms clearly outperform Algorithm ${\mathrm{A}}_m$ in terms of solution quality. On the first dataset with known optimal values the average relative error ranges from 1.47% over optimum (algorithm ${\mathrm{A}}_m$) to 0.08% over optimum (algorithm ${\mathrm{E}}_m$). On the second dataset with known optimal values the average relative error ranges from 4.41% over optimum (algorithm ${\mathrm{A}}_m$) to 0.45% over optimum (algorithm ${\mathrm{F}}_m$). Better quality of solutions demands higher computation times, thus the new algorithms provide a good compromise between quality of solutions and computation time.

Khovanov homology, an invariant of links in ${ \mathbb{R} }^{3} $ , is a graded homology theory that categorifies the Jones polynomial in the sense that the graded Euler characteristic of the homology is the Jones polynomial. Asaeda et al. [‘Categorification of the Kauffman bracket skein module of $I$ -bundles over surfaces’, Algebr. Geom. Topol. 4 (2004), 1177–1210] generalised this construction by defining a double graded homology theory that categorifies the Kauffman bracket skein module of links in $I$ -bundles over surfaces, except for the surface $ \mathbb{R} {\mathrm{P} }^{2} $ , where the construction fails due to strange behaviour of links when projected to the nonorientable surface $ \mathbb{R} {\mathrm{P} }^{2} $ . This paper categorifies the missing case of the twisted $I$ -bundle over $ \mathbb{R} {\mathrm{P} }^{2} $ , $ \mathbb{R} {\mathrm{P} }^{2} \widetilde {\times } I\approx \mathbb{R} {\mathrm{P} }^{3} \setminus \{ \ast \} $ , by redefining the differential in the Khovanov chain complex in a suitable manner.

In this paper, we extend the definition of a knotoid to multi-linkoids that consist of a finite number of knot and knotoid components. We study invariants of multi-linkoids, such as the Kauffman bracket polynomial, ordered bracket polynomial, the Kauffman skein module, and the T-invariant in relation with generalized $$\Theta $$Θ -graphs.

We obtain new results on independent 2- and 3-rainbow domination numbers of generalized Petersen graphs $P(n,k)$ for certain values of $n,k\in \mathbb{N}$ . By suitably adjusting and applying a well established technique of tropical algebra (path algebra) we obtain exact 2-independent rainbow domination numbers of generalized Petersen graphs $P(n,2)$ and $P(n,3)$ thus confirming a conjecture proposed by Shao et al. In addition, we compute exact 3-independent rainbow domination numbers of generalized Petersen graphs $P(n,2)$ . The method used here is developed for rainbow domination and for Petersen graphs. However, with some natural modifications, the method used can be applied to other domination type invariants, and to many other classes of graphs including grids and tori.