Roman domination is an historically inspired variety of domination in graphs, in which vertices are assigned a value from the set $\{0,1,2\}$ in such a way that every vertex assigned the value 0 is adjacent to a vertex assigned the value 2. The Roman domination number is the minimum possible sum of all values in such an assignment. Using an algebraic approach we present an $O(C)$-time algorithm for computing the Roman domination numbers of special classes of graphs called polygraphs, which include rotagraphs and fasciagraphs. Using this algorithm we determine formulas for the Roman domination numbers of the Cartesian products of the form $P_n\Box P_k$, $P_n\Box C_k$, for $k\leq8$ and $n \in {\mathbb N}$, and $C_n\Box P_k$ and $C_n\Box C_k$, for $k\leq 6$ and $n \in {\mathbb N}$, for paths $P_n$ and cycles $C_n$. We also find all special graphs called Roman graphs in these families of graphs.

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.

The discharging method is most well-known for its central role in the proof of the Four Color Theorem. This proof technique was extensively applied to study various graph coloring problems, in particular on planar graphs. In this paper, we show that suitably altered discharging technique can also be used on domination type problems. The general discharging approach for domination type problems is illustrated on a specific domination type problem, the double Roman domination on some generalized Petersen graphs. By applying this approach, we first prove that γ dR(G) ≥ 3n/Δ(G)+1 for any connected graph G with n ≥ 2 vertices. As examples we also determine the exact values of the double Roman domination numbers of the generalized Petersen graphs P(n,1) and the double generalized Petersen graphs DP(n,1). The obtained results imply that P(n,1) is double Roman if and only if n 6≢ 2 (mod 4) and DP(n,1) is double Roman if and only if n ≡ 0 (mod 4).

We provide several examples showing that local search, the most basic metaheuristics, may be a very competitive choice for solving computationally hard optimization problems. In addition, generation of starting solutions by greedy heuristics should be at least considered as one of very natural possibilities. In this critical survey, selected examples discussed include the traveling salesman, the resource-constrained project scheduling, the channel assignment, and computation of bounds for the Shannon capacity.