Dominating sets and domatic number of circular arc graphs
This paper presents an O(n\(| E|)\) time algorithm for finding a minimum cardinality dominating set of a circular arc graph. The domatic number problem (finding a maximum cardinality partition of the nodes into dominating sets) is solved in \(O(n^ 2 \log n)\) time for a proper circular arc graph, and it is shown NP-complete for general circular arc graphs.
scientific article; zbMATH DE number 3926969
scientific article