DOMINATION ON COCOMPARABILITY GRAPHS

被引：86

作者：

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

共 50 条

[1] Weighted domination of cocomparability graphs
Chang, MS
DISCRETE APPLIED MATHEMATICS, 1997, 80 (2-3) : 135 - 148
[2] WEIGHTED INDEPENDENT PERFECT DOMINATION ON COCOMPARABILITY GRAPHS
CHANG, GJ
RANGAN, CP
COORG, SR
DISCRETE APPLIED MATHEMATICS, 1995, 63 (03) : 215 - 222
[3] DISTANCES IN COCOMPARABILITY GRAPHS AND THEIR POWERS
DAMASCHKE, P
DISCRETE APPLIED MATHEMATICS, 1992, 35 (01) : 67 - 72
[4] Node packings on cocomparability graphs
Barcia, P
Cerdeira, JO
OPERATIONS RESEARCH LETTERS, 2003, 31 (05) : 341 - 342
[5] On the intersection of tolerance and cocomparability graphs
Mertzios, George B.
Zaks, Shmuel
DISCRETE APPLIED MATHEMATICS, 2016, 199 : 46 - 88
[6] On the Intersection of Tolerance and Cocomparability Graphs
Mertzios, George B.
Zaks, Shmuel
ALGORITHMS AND COMPUTATION, PT I, 2010, 6506 : 230 - 240
[7] A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs
Takaoka, Asahi
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105A (09) : 1223 - 1227
[8] HAMILTONIAN CYCLE IS POLYNOMIAL ON COCOMPARABILITY GRAPHS
DEOGUN, JS
STEINER, G
DISCRETE APPLIED MATHEMATICS, 1992, 39 (02) : 165 - 172
[9] A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs
Takaoka, Asahi
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105 (08)
[10] BIPARTITE ANALOGUES OF COMPARABILITY AND COCOMPARABILITY GRAPHS
Hell, Pavol
Huang, Jing
Lin, Jephian C-H
McConnell, Ross M.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (03) : 1969 - 1983

← 1 2 3 4 5 →