DOMINATION ON COCOMPARABILITY GRAPHS

Authors
KRATSCH D STEWART L
Citation
D. Kratsch et L. Stewart, DOMINATION ON COCOMPARABILITY GRAPHS, SIAM journal on discrete mathematics, 6(3), 1993, pp. 400-417
Citations number
27
Categorie Soggetti
Mathematics,Mathematics
Journal title
SIAM journal on discrete mathematics → ACNP
ISSN journal
08954801
Volume
6
Issue
3
Year of publication
1993
Pages
400 - 417
Database
ISI
SICI code
0895-4801(1993)6:3<400:DOCG>2.0.ZU;2-I
Abstract
The authors determine the algorithmic complexity of domination and var iants 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 CLIQ UE and MINIMUM DOMiNATING CLIQUE remain NP-complete on cocomparability graphs.