A dominating set of a graph G = (N,E) is a subset S of nodes such that every node is either in S or adjacent to a node which is in S. The domatic number of G is the size of a maximum cardinality partition of N into dominating sets. The problems of finding a minimum cardinality dominating set and the domatic number are both NP-complete even for special classes of graphs. In the present paper we give an O(n{divides}E{divides}) time algorithm that finds a minimum cardinality dominating set when G is a circular arc graph (intersection graph of arcs on a circle). The domatic number problem is solved in O(n2 log n) time when G is a proper circular arc graph, and it is shown NP-complete for general circular arc graphs
Autori interni: | ||
Autori: | BONUCCELLI M | |
Titolo: | DOMINATING SETS AND DOMATIC NUMBER OF CIRCULAR ARC GRAPHS | |
Anno del prodotto: | 1985 | |
Digital Object Identifier (DOI): | 10.1016/0166-218X(85)90025-3 | |
Appare nelle tipologie: | 1.1 Articolo in rivista |