Dominating sets and domatic number of circular arc graphs |
| |
Authors: | Maurizio A Bonuccelli |
| |
Institution: | Dipartimento di Informatica, Università di Pisa, Pisa, Italy |
| |
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∣E∣) 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. |
| |
Keywords: | Dominating set domatic number circular arc graph NP-complete |
本文献已被 ScienceDirect 等数据库收录! |