DOMINATION ON COCOMPARABILITY GRAPHS

被引：87
作者：
KRATSCH, D
STEWART, L
机构：
[1] UNIV ALBERTA,DEPT COMP SCI,EDMONTON T6G 2H1,AB,CANADA
[2] UNIV TORONTO,TORONTO M5S 1A1,ONTARIO,CANADA
来源：
SIAM JOURNAL ON DISCRETE MATHEMATICS | 1993年 / 6卷 / 03期
关键词：
DOMINATION; COCOMPARABILITY GRAPHS; GRAPH ALGORITHMS;
D O I：
10.1137/0406032
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：400 / 417
页数：18
相关论文
共 27 条
[1]  
[Anonymous], 1983, DATA STRUCTURES NETW, DOI DOI 10.1137/1.9781611970265
[2]  
Berge C, 1985, GRAPHS
[3]   TOTAL DOMINATION IN INTERVAL-GRAPHS [J].
BERTOSSI, AA .
INFORMATION PROCESSING LETTERS, 1986, 23 (03) :131-134
[4]   DOMINATING SETS IN CHORDAL GRAPHS [J].
BOOTH, KS ;
JOHNSON, JH .
SIAM JOURNAL ON COMPUTING, 1982, 11 (01) :191-199
[5]   ON DOMINATION PROBLEMS FOR PERMUTATION AND OTHER GRAPHS [J].
BRANDSTADT, A ;
KRATSCH, D .
THEORETICAL COMPUTER SCIENCE, 1987, 54 (2-3) :181-198
[6]  
BRANDSTADT A, 1985, P FCT 85, P53
[7]   PERMUTATION GRAPHS - CONNECTED DOMINATION AND STEINER TREES [J].
COLBOURN, CJ ;
STEWART, LK .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :179-189
[8]  
COLBOURN CJ, 1989, COMMUNICATION
[9]   CLUSTERING AND DOMINATION IN PERFECT GRAPHS [J].
CORNEIL, DG ;
PERL, Y .
DISCRETE APPLIED MATHEMATICS, 1984, 9 (01) :27-39
[10]   DOMINATING SETS IN PERFECT GRAPHS [J].
CORNEIL, DG ;
STEWART, LK .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :145-164
123