zbMATH — the first resource for mathematics

Efficient algorithms for the domination problems on interval and circular-arc graphs. (English) Zbl 0911.05051
A 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.

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
Full Text: DOI