Dominating sets and domatic number of circular arc graphs (Q1066921)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Dominating sets and domatic number of circular arc graphs |
scientific article; zbMATH DE number 3926969
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Dominating sets and domatic number of circular arc graphs |
scientific article; zbMATH DE number 3926969 |
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
