Dominating sets and domatic number of circular arc graphs (Q1066921)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Dominating sets and domatic number of circular arc graphs |
scientific article |
Statements
Dominating sets and domatic number of circular arc graphs (English)
0 references
1985
0 references
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.
0 references
circular arc graph
0 references
domatic number
0 references
dominating sets
0 references
0 references
