# 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.

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