Efficient algorithms for the domination problems on interval and circular-arc graphs.

*(English)*Zbl 0911.05051A subset \(S\) of the vertex set of a graph \(G\) is called dominating, if each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). If each vertex of \(G\) is adjacent to a vertex of \(S\), then \(S\) is a total dominating set. If a dominating set in \(G\) induces a connected subgraph of \(G\), it is called a connected dominating set. An interval graph is the intersection graph of a set of intervals on a real line; similarly a circular-arc graph is the intersection graph of a set of arcs of a circle. For such graphs some algorithms are presented for finding a dominating set, a total dominating set, and a connected dominating set of minimum weight, provided that weights are assigned to the vertices. For an interval graph with sorted endpoints (defined in the paper) the algorithms run in time \(O(n)\) or \(O(n\log\log n)\), for a circular-arc graph in time \(O(n+ m)\), where \(n\) is the number of vertices and \(m\) is the number of edges.

Reviewer: B.Zelinka (Liberec)

##### MSC:

05C85 | Graph algorithms (graph-theoretic aspects) |

68Q25 | Analysis of algorithms and problem complexity |

68W10 | Parallel algorithms in computer science |

68R10 | Graph theory (including graph drawing) in computer science |

90C27 | Combinatorial optimization |