Abstract: The authors determine the algorithmic complexity of domination and variants on cocomparability graphs, a class of perfect graphs containing both the interval and the permutation graphs. Minimum dominating, total dominating, connected dominating, and independent dominating sets can be constructed in polynomial time. On the other hand, DOMINATING CLIQUE and MINIMUM DOMINATING CLIQUE remain NP-complete on cocomparability graphs.
Publication Year: 1993
Publication Date: 1993-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 150
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot