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
DOMINATING SETS AND DOMATIC NUMBER OF CIRCULAR ARC GRAPHS
BONUCCELLI, MAURIZIO ANGELO
1985-01-01
Abstract
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 graphsI documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
