Algorithms of the Domination Lab

University of Bojnord

The idea, pseudocode, analysis and references of every algorithm used in the lab. Formulas are typeset with LaTeX notation (MathJax), and each pseudocode comes with its LaTeX source.

Contents

  1. Greedy dominating set
  2. Greedy total dominating set
  3. Connected dominating set (greedy growth)
  4. Paired dominating set (greedy pairs)
  5. 2-dominating set (greedy)
  6. Roman domination from a greedy dominating set
  7. Vertex cover: 2-approximation by a maximal matching
  8. Greedy maximal independent set (smallest degree first)
  9. Greedy independent dominating set (largest degree first)
  10. Exact answers (bit masks, up to 20 vertices)
  11. Domatic partition
  12. Checking your selection
  13. Unit disk graphs
  14. Reading Ipe files

Printable versions of this page, typeset with LaTeX: PDF (English), PDF (Persian), and the sources .tex (English), .tex (Persian, XeLaTeX with xepersian).

Notation

Throughout, \(G=(V,E)\) is a simple undirected graph with \(n=|V|\) vertices and \(m=|E|\) edges. \(N(v)\) is the set of neighbors of \(v\), \(N[v]=N(v)\cup\{v\}\), and for a set \(X\) we write \(N[X]=\bigcup_{v\in X}N[v]\). \(\Delta\) and \(\delta\) are the maximum and minimum degree, and \(H(k)=\sum_{i=1}^{k}1/i\le \ln k+1\) is the harmonic number. The parameters computed by the lab are \(\gamma\) (domination), \(\gamma_t\) (total), \(\gamma_c\) (connected), \(i\) (independent domination), \(\gamma_{pr}\) (paired), \(\gamma_{\times 2}\) (\(2\)-domination), \(\gamma_p\) (perfect), \(\alpha\) (independence), \(\beta\) (vertex cover), \(\gamma_R\) (Roman) and \(d\) (domatic number); see [11]. These problems are NP-hard on general graphs (for the classical ones see [8]), which is why the lab uses heuristics for large graphs and exhaustive search for small ones.

1. Greedy dominating set

A vertex \(v\) covers the set \(N[v]\), so finding a dominating set is a set cover problem on the universe \(V\). The greedy rule repeatedly takes the vertex that covers the largest number of vertices that are not covered yet.
Input: graph \(G=(V,E)\)   Output: a dominating set \(S\)
Algorithm 1   Greedy-Dominating-Set
  1. \(S\gets\emptyset\); \(C\gets\emptyset\) ▷ \(C\) = covered vertices
  2. while \(C\neq V\) do
  3. pick \(v\) maximizing \(|N[v]\setminus C|\)
  4. \(S\gets S\cup\{v\}\); \(C\gets C\cup N[v]\)
  5. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-Dominating-Set}\label{alg:a0}
\begin{algorithmic}[1]
  \Require graph $G=(V,E)$
  \Ensure a dominating set $S$
\State $S\gets\emptyset$;\ $C\gets\emptyset$ \Comment{$C$ = covered vertices}
\While{$C\neq V$}
  \State pick $v$ maximizing $|N[v]\setminus C|$
  \State $S\gets S\cup\{v\}$;\ $C\gets C\cup N[v]$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

2. Greedy total dominating set

In a total dominating set every vertex, including those in \(S\), needs a neighbor in \(S\). A vertex therefore covers only its open neighborhood \(N(v)\), and the greedy idea is again set cover. If some vertex has no neighbor, no total dominating set exists [13].
Input: graph \(G\)   Output: a total dominating set, or a message that none exists
Algorithm 2   Greedy-Total-Dominating-Set
  1. \(S\gets\emptyset\); \(C\gets\emptyset\)
  2. while \(C\neq V\) do
  3. pick \(v\) maximizing \(|N(v)\setminus C|\)
  4. if \(|N(v)\setminus C|=0\) then ▷ some vertex has no neighbor
  5. return “no total dominating set”
  6. \(S\gets S\cup\{v\}\); \(C\gets C\cup N(v)\)
  7. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-Total-Dominating-Set}\label{alg:a1}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure a total dominating set, or a message that none exists
\State $S\gets\emptyset$;\ $C\gets\emptyset$
\While{$C\neq V$}
  \State pick $v$ maximizing $|N(v)\setminus C|$
  \If{$|N(v)\setminus C|=0$} \Comment{some vertex has no neighbor}
    \State \Return \textrm{``no total dominating set''}
  \EndIf
  \State $S\gets S\cup\{v\}$;\ $C\gets C\cup N(v)$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

3. Connected dominating set (greedy growth)

Start from a vertex of maximum degree. At each step add a vertex that is already dominated, i.e. adjacent to \(S\), and that dominates the most new vertices. Because every new vertex touches \(S\), the induced subgraph \(G[S]\) stays connected. If no such vertex exists before everything is dominated, \(G\) is disconnected. Guha and Khuller [9] analyse this kind of greedy growth: they show that the naive rule can perform badly, and that a variant which also looks at pairs of vertices (a dominated vertex together with a white neighbor) achieves \(2(1+H(\Delta))\). The lab runs the simple rule, so no approximation ratio is claimed for it.
Input: connected graph \(G\)   Output: a connected dominating set \(S\)
Algorithm 3   Greedy-CDS
  1. \(v\gets\) vertex of maximum degree; \(S\gets\{v\}\); \(C\gets N[v]\)
  2. while \(C\neq V\) do
  3. pick \(u\in C\setminus S\) maximizing \(|N(u)\setminus C|\)
  4. if \(|N(u)\setminus C|=0\) then ▷ \(G\) is disconnected
  5. return “disconnected”
  6. \(S\gets S\cup\{u\}\); \(C\gets C\cup N[u]\)
  7. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-CDS}\label{alg:a2}
\begin{algorithmic}[1]
  \Require connected graph $G$
  \Ensure a connected dominating set $S$
\State $v\gets$ vertex of maximum degree;\ $S\gets\{v\}$;\ $C\gets N[v]$
\While{$C\neq V$}
  \State pick $u\in C\setminus S$ maximizing $|N(u)\setminus C|$
  \If{$|N(u)\setminus C|=0$} \Comment{$G$ is disconnected}
    \State \Return \textrm{``disconnected''}
  \EndIf
  \State $S\gets S\cup\{u\}$;\ $C\gets C\cup N[u]$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

4. Paired dominating set (greedy pairs)

A paired dominating set is a dominating set whose induced subgraph has a perfect matching [12]. Take a vertex \(u\) that is not dominated yet, pair it with the neighbor \(w\) that covers the most new vertices, and add both. Each pair is an edge, so the chosen pairs form a perfect matching of \(G[S]\) by construction. A vertex without neighbors makes the problem unsolvable.
Input: graph \(G\)   Output: a paired dominating set, or a message that none exists
Algorithm 4   Greedy-Paired-Dominating-Set
  1. \(S\gets\emptyset\); \(C\gets\emptyset\)
  2. while \(C\neq V\) do
  3. \(u\gets\) any vertex of \(V\setminus C\)
  4. if \(N(u)=\emptyset\) then
  5. return “no paired dominating set”
  6. \(w\gets\) neighbor of \(u\) maximizing \(|N[w]\setminus C|\)
  7. \(S\gets S\cup\{u,w\}\); \(C\gets C\cup N[u]\cup N[w]\)
  8. return \(S\) ▷ the edges \(uw\) form a perfect matching of \(G[S]\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-Paired-Dominating-Set}\label{alg:a3}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure a paired dominating set, or a message that none exists
\State $S\gets\emptyset$;\ $C\gets\emptyset$
\While{$C\neq V$}
  \State $u\gets$ any vertex of $V\setminus C$
  \If{$N(u)=\emptyset$}
    \State \Return \textrm{``no paired dominating set''}
  \EndIf
  \State $w\gets$ neighbor of $u$ maximizing $|N[w]\setminus C|$
  \State $S\gets S\cup\{u,w\}$;\ $C\gets C\cup N[u]\cup N[w]$
\EndWhile
\State \Return $S$ \Comment{the edges $uw$ form a perfect matching of $G[S]$}
\end{algorithmic}
\end{algorithm}

5. 2-dominating set (greedy)

In a \(2\)-dominating set every vertex outside \(S\) has at least two neighbors in \(S\) [6]. For each vertex we count how many neighbors it is still missing, and at each step we add the vertex that removes the most missing neighbors: its own need disappears, and every neighbor outside \(S\) that still needs help gets one step closer.
Input: graph \(G\)   Output: a \(2\)-dominating set \(S\)
Algorithm 5   Greedy-2-Dominating-Set
  1. \(S\gets\emptyset\) ▷ \(\mathrm{def}(v)=0\) if \(v\in S\), else \(\max\{0,\,2-|N(v)\cap S|\}\)
  2. while \(\sum_{v}\mathrm{def}(v)>0\) do
  3. pick \(x\notin S\) maximizing \(\mathrm{def}(x)+|\{u\in N(x)\setminus S:\mathrm{def}(u)>0\}|\)
  4. \(S\gets S\cup\{x\}\)
  5. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-2-Dominating-Set}\label{alg:a4}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure a $2$-dominating set $S$
\State $S\gets\emptyset$ \Comment{$\mathrm{def}(v)=0$ if $v\in S$, else $\max\{0,\,2-|N(v)\cap S|\}$}
\While{$\sum_{v}\mathrm{def}(v)>0$}
  \State pick $x\notin S$ maximizing $\mathrm{def}(x)+|\{u\in N(x)\setminus S:\mathrm{def}(u)>0\}|$
  \State $S\gets S\cup\{x\}$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

6. Roman domination from a greedy dominating set

A Roman dominating function is a labeling \(f:V\to\{0,1,2\}\) such that every vertex with \(f(v)=0\) has a neighbor \(u\) with \(f(u)=2\); its weight is \(\sum_v f(v)\) and \(\gamma_R\) is the minimum weight [3, 16]. Labeling a dominating set \(S\) with \(2\) and everything else with \(0\) gives weight \(2|S|\). The improvement step lowers a \(2\) to a \(1\) when this is safe.
Input: graph \(G\)   Output: a Roman dominating function \(f\)
Algorithm 6   Roman-From-Greedy-DS
  1. \(S\gets\) Greedy-Dominating-Set\((G)\)
  2. \(f(v)\gets2\) for \(v\in S\); \(f(v)\gets0\) otherwise
  3. for \(v\in S\) do ▷ improvement step
  4. if every \(u\in N(v)\) with \(f(u)=0\) has some \(w\in N(u)\setminus\{v\}\) with \(f(w)=2\) then
  5. \(f(v)\gets1\)
  6. return \(f\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Roman-From-Greedy-DS}\label{alg:a5}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure a Roman dominating function $f$
\State $S\gets$ Greedy-Dominating-Set$(G)$
\State $f(v)\gets2$ for $v\in S$;\ $f(v)\gets0$ otherwise
\For{$v\in S$} \Comment{improvement step}
  \If{every $u\in N(v)$ with $f(u)=0$ has some $w\in N(u)\setminus\{v\}$ with $f(w)=2$}
    \State $f(v)\gets1$
  \EndIf
\EndFor
\State \Return $f$
\end{algorithmic}
\end{algorithm}

7. Vertex cover: 2-approximation by a maximal matching

Scan the edges. Whenever an edge has no endpoint in the cover yet, put both endpoints in. The edges that triggered this are pairwise disjoint, so they form a maximal matching \(M\) [5].
Input: graph \(G=(V,E)\)   Output: a vertex cover \(C\)
Algorithm 7   Matching-Vertex-Cover
  1. \(C\gets\emptyset\)
  2. for each edge \(uv\in E\) (in input order) do
  3. if \(u\notin C\) and \(v\notin C\) then
  4. \(C\gets C\cup\{u,v\}\)
  5. return \(C\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Matching-Vertex-Cover}\label{alg:a6}
\begin{algorithmic}[1]
  \Require graph $G=(V,E)$
  \Ensure a vertex cover $C$
\State $C\gets\emptyset$
\For{each edge $uv\in E$ (in input order)}
  \If{$u\notin C$ and $v\notin C$}
    \State $C\gets C\cup\{u,v\}$
  \EndIf
\EndFor
\State \Return $C$
\end{algorithmic}
\end{algorithm}

8. Greedy maximal independent set (smallest degree first)

Repeatedly take a vertex of smallest degree in what is left of the graph, add it to \(S\), and delete it together with its neighbors. Taking low-degree vertices first deletes few vertices per step, which usually leaves room for a larger set.
Input: graph \(G\)   Output: a maximal independent set \(S\)
Algorithm 8   Greedy-Independent-Set
  1. \(S\gets\emptyset\); \(H\gets G\)
  2. while \(V(H)\neq\emptyset\) do
  3. \(v\gets\) vertex of minimum degree in \(H\)
  4. \(S\gets S\cup\{v\}\); \(H\gets H-N_H[v]\)
  5. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-Independent-Set}\label{alg:a7}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure a maximal independent set $S$
\State $S\gets\emptyset$;\ $H\gets G$
\While{$V(H)\neq\emptyset$}
  \State $v\gets$ vertex of minimum degree in $H$
  \State $S\gets S\cup\{v\}$;\ $H\gets H-N_H[v]$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

9. Greedy independent dominating set (largest degree first)

An independent dominating set is exactly a maximal independent set [4]: a maximal independent set is dominating (otherwise another vertex could be added), and a dominating independent set is maximal. To keep the set small, this variant takes a vertex of largest degree first, so that each step deletes as many vertices as possible.
Input: graph \(G\)   Output: an independent dominating set \(S\)
Algorithm 9   Greedy-Independent-Dominating-Set
  1. \(S\gets\emptyset\); \(H\gets G\)
  2. while \(V(H)\neq\emptyset\) do
  3. \(v\gets\) vertex of maximum degree in \(H\)
  4. \(S\gets S\cup\{v\}\); \(H\gets H-N_H[v]\)
  5. return \(S\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Greedy-Independent-Dominating-Set}\label{alg:a8}
\begin{algorithmic}[1]
  \Require graph $G$
  \Ensure an independent dominating set $S$
\State $S\gets\emptyset$;\ $H\gets G$
\While{$V(H)\neq\emptyset$}
  \State $v\gets$ vertex of maximum degree in $H$
  \State $S\gets S\cup\{v\}$;\ $H\gets H-N_H[v]$
\EndWhile
\State \Return $S$
\end{algorithmic}
\end{algorithm}

10. Exact answers (bit masks, up to 20 vertices)

Because these problems are NP-hard [8], exact answers take exponential time. For \(n\le 20\) the lab looks at every subset \(X\subseteq V\), written as a bit mask. Two tables are filled once by dynamic programming over the masks: the closed neighborhood \(N[X]\) of each subset, and whether \(X\) is independent. Afterwards each problem is a quick test on a subset, and subsets that cannot beat the best answer found so far are skipped.
Input: graph \(G\) with \(n\le20\), a problem \(P\)   Output: an optimal set for \(P\), if one exists
Algorithm 10   Exact-Search
  1. for \(X=1,\dots,2^n-1\), with \(x\) the lowest vertex of \(X\) do
  2. \(\mathrm{cl}[X]\gets\mathrm{cl}[X\setminus\{x\}]\cup N[x]\)
  3. \(\mathrm{ind}[X]\gets\mathrm{ind}[X\setminus\{x\}]\wedge(N(x)\cap X=\emptyset)\)
  4. \(\mathit{best}\gets\text{none}\)
  5. for \(X\subseteq V\) do
  6. if \(|X|\) cannot improve \(|\mathit{best}|\) then
  7. continue
  8. if \(\mathrm{Test}_P(X)\) then
  9. \(\mathit{best}\gets X\)
  10. return \(\mathit{best}\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Exact-Search}\label{alg:exact}
\begin{algorithmic}[1]
  \Require graph $G$ with $n\le20$, a problem $P$
  \Ensure an optimal set for $P$, if one exists
\For{$X=1,\dots,2^n-1$, with $x$ the lowest vertex of $X$}
  \State $\mathrm{cl}[X]\gets\mathrm{cl}[X\setminus\{x\}]\cup N[x]$
  \State $\mathrm{ind}[X]\gets\mathrm{ind}[X\setminus\{x\}]\wedge(N(x)\cap X=\emptyset)$
\EndFor
\State $\mathit{best}\gets\text{none}$
\For{$X\subseteq V$}
  \If{$|X|$ cannot improve $|\mathit{best}|$}
    \State continue
  \EndIf
  \If{$\mathrm{Test}_P(X)$}
    \State $\mathit{best}\gets X$
  \EndIf
\EndFor
\State \Return $\mathit{best}$
\end{algorithmic}
\end{algorithm}

11. Domatic partition

The domatic number \(d(G)\) is the largest number of pairwise disjoint dominating sets; it satisfies \(d(G)\le\delta+1\) [4]. Every dominating set contains a minimal dominating set, so it is enough to find all minimal dominating sets and to search, by backtracking, for the largest family of pairwise disjoint ones.
Input: graph \(G\) with \(n\le20\)   Output: disjoint dominating sets \(D_1,\dots,D_k\)
Algorithm 11   Domatic-Partition
  1. \(\mathcal M\gets\) all minimal dominating sets of \(G\); \(\mathit{best}\gets\emptyset\)
  2. Search\((s,\ U,\ \mathcal F)\) ▷ backtracking over \(\mathcal M\)
  3. if \(|\mathcal F|>|\mathit{best}|\) then
  4. \(\mathit{best}\gets\mathcal F\)
  5. if \(|\mathit{best}|=\delta+1\) or the step limit is reached then
  6. return stop
  7. for \(D\in\mathcal M\) from index \(s\) with \(D\cap U=\emptyset\) do
  8. Search\((\text{next},\ U\cup D,\ \mathcal F+[D])\)
  9. add vertices that are in no set to \(D_1\)
  10. return \(\mathit{best}\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Domatic-Partition}\label{alg:domatic}
\begin{algorithmic}[1]
  \Require graph $G$ with $n\le20$
  \Ensure disjoint dominating sets $D_1,\dots,D_k$
\State $\mathcal M\gets$ all minimal dominating sets of $G$;\ $\mathit{best}\gets\emptyset$
\State Search$(s,\ U,\ \mathcal F)$ \Comment{backtracking over $\mathcal M$}
  \If{$|\mathcal F|>|\mathit{best}|$}
    \State $\mathit{best}\gets\mathcal F$
  \EndIf
  \If{$|\mathit{best}|=\delta+1$ or the step limit is reached}
    \State \Return stop
  \EndIf
  \For{$D\in\mathcal M$ from index $s$ with $D\cap U=\emptyset$}
    \State Search$(\text{next},\ U\cup D,\ \mathcal F+[D])$
  \EndFor
\State add vertices that are in no set to $D_1$
\State \Return $\mathit{best}$
\end{algorithmic}
\end{algorithm}

12. Checking your selection

Whatever you select, the lab counts for every vertex how many of its neighbors are in \(S\) (and, for Roman domination, how many have label \(2\)) and compares this with the definition. Connectivity of \(G[S]\) is tested with a graph search; the perfect matching of paired domination with a short backtracking search (up to \(|S|=24\)).
Input: graph \(G\), a selection \(S\) (or labels \(f\)), a problem \(P\)   Output: the vertices and edges that violate the definition
Algorithm 12   Check-Selection
  1. for \(v\in V\) do
  2. \(k(v)\gets|N(v)\cap S|\)
  3. for \(v\in V\) do
  4. compare \(k(v)\) with the definition of \(P\) ▷ e.g. \(v\in S\) or \(k(v)\ge1\)
  5. for \(uv\in E\) do
  6. check independence / cover conditions on \(u,v\)
  7. test connectivity or a perfect matching of \(G[S]\) if \(P\) requires it

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Check-Selection}\label{alg:check}
\begin{algorithmic}[1]
  \Require graph $G$, a selection $S$ (or labels $f$), a problem $P$
  \Ensure the vertices and edges that violate the definition
\For{$v\in V$}
  \State $k(v)\gets|N(v)\cap S|$
\EndFor
\For{$v\in V$}
  \State compare $k(v)$ with the definition of $P$ \Comment{e.g. $v\in S$ or $k(v)\ge1$}
\EndFor
\For{$uv\in E$}
  \State check independence / cover conditions on $u,v$
\EndFor
\State test connectivity or a perfect matching of $G[S]$ if $P$ requires it
\end{algorithmic}
\end{algorithm}

13. Unit disk graphs

In unit disk mode the lab rebuilds the edges every time a vertex moves: two vertices are adjacent when their Euclidean distance is at most the radius \(r\) [2].
Input: points \(p_1,\dots,p_n\) in the plane, radius \(r\)   Output: the graph \(G=(V,E)\)
Algorithm 13   Unit-Disk-Graph
  1. \(E\gets\emptyset\)
  2. for all pairs \(i<j\) do
  3. if \(\lVert p_i-p_j\rVert\le r\) then
  4. add the edge \(ij\) to \(E\)
  5. return \((V,E)\)

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Unit-Disk-Graph}\label{alg:udg}
\begin{algorithmic}[1]
  \Require points $p_1,\dots,p_n$ in the plane, radius $r$
  \Ensure the graph $G=(V,E)$
\State $E\gets\emptyset$
\For{all pairs $i<j$}
  \If{$\lVert p_i-p_j\rVert\le r$}
    \State add the edge $ij$ to $E$
  \EndIf
\EndFor
\State \Return $(V,E)$
\end{algorithmic}
\end{algorithm}

14. Reading Ipe files

Ipe [17] stores a drawing as XML. The lab turns marks and small circles into vertices, and every segment of a polyline or polygon into an edge between the vertices nearest to its two endpoints (within a small tolerance). An endpoint with no vertex nearby becomes a new vertex. Transformations of groups are applied, and the result is scaled to fit the canvas.
Input: an Ipe XML file   Output: a graph \(G\)
Algorithm 14   Read-Ipe
  1. \(V\gets\) all marks and small circles (after group transformations)
  2. for each polyline or polygon and each consecutive pair of points \(p,q\) do
  3. \(a\gets\) vertex nearest to \(p\) within tolerance, else a new vertex at \(p\)
  4. \(b\gets\) the same for \(q\)
  5. if \(a\neq b\) then
  6. add the edge \(ab\) (once)
  7. scale and center everything to fit the canvas

Analysis

LaTeX source (algpseudocode)
\begin{algorithm}[t]
\caption{Read-Ipe}\label{alg:ipe}
\begin{algorithmic}[1]
  \Require an Ipe XML file
  \Ensure a graph $G$
\State $V\gets$ all marks and small circles (after group transformations)
\For{each polyline or polygon and each consecutive pair of points $p,q$}
  \State $a\gets$ vertex nearest to $p$ within tolerance, else a new vertex at $p$
  \State $b\gets$ the same for $q$
  \If{$a\neq b$}
    \State add the edge $ab$ (once)
  \EndIf
\EndFor
\State scale and center everything to fit the canvas
\end{algorithmic}
\end{algorithm}

References

  1. Chvátal, V.: A greedy heuristic for the set-covering problem. Mathematics of Operations Research 4(3), 233–235 (1979)
  2. Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit disk graphs. Discrete Mathematics 86(1–3), 165–177 (1990)
  3. Cockayne, E.J., Dreyer Jr., P.A., Hedetniemi, S.M., Hedetniemi, S.T.: Roman domination in graphs. Discrete Mathematics 278(1–3), 11–22 (2004)
  4. Cockayne, E.J., Hedetniemi, S.T.: Towards a theory of domination in graphs. Networks 7(3), 247–261 (1977)
  5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 4th edn. MIT Press (2022)
  6. Fink, J.F., Jacobson, M.S.: \(n\)-domination in graphs. In: Graph Theory with Applications to Algorithms and Computer Science, pp. 283–300. Wiley, New York (1985)
  7. Gallai, T.: Über extreme Punkt- und Kantenmengen. Annales Universitatis Scientiarum Budapestinensis, Sectio Mathematica 2, 133–138 (1959)
  8. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)
  9. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998) doi:10.1007/PL00009201
  10. Halldórsson, M.M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. Algorithmica 18(1), 145–163 (1997) doi:10.1007/BF02523693
  11. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Marcel Dekker, New York (1998)
  12. Haynes, T.W., Slater, P.J.: Paired-domination in graphs. Networks 32(3), 199–206 (1998)
  13. Henning, M.A., Yeo, A.: Total Domination in Graphs. Springer Monographs in Mathematics, Springer (2013)
  14. Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences 9(3), 256–278 (1974)
  15. Lovász, L.: On the ratio of optimal integral and fractional covers. Discrete Mathematics 13(4), 383–390 (1975)
  16. Stewart, I.: Defend the Roman Empire! Scientific American 281(6), 136–139 (1999)
  17. Cheong, O.: Ipe, the extensible drawing editor. https://ipe.otfried.org