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 条
  • [11] Linear Time LexDFS on Cocomparability Graphs
    Koehler, Ekkehard
    Mouatadid, Lalla
    ALGORITHM THEORY - SWAT 2014, 2014, 8503 : 319 - +
  • [12] FEEDBACK VERTEX SET ON COCOMPARABILITY GRAPHS
    COORG, SR
    RANGAN, CP
    NETWORKS, 1995, 26 (02) : 101 - 111
  • [13] ON THE POWER OF GRAPH SEARCHING FOR COCOMPARABILITY GRAPHS
    Corneil, Derek G.
    Dusart, Jeremie
    Habib, Michel
    Koehler, Ekkehard
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2016, 30 (01) : 569 - 591
  • [14] Counting independent sets in cocomparability graphs
    Dyer, Martin
    Mueller, Haiko
    INFORMATION PROCESSING LETTERS, 2019, 144 : 31 - 36
  • [15] The Longest Path Problem is Polynomial on Cocomparability Graphs
    Ioannidou, Kyriaki
    Nikolopoulos, Stavros D.
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 6410 : 27 - 38
  • [16] 1-tough cocomparability graphs are Hamiltonian
    Deogun, JS
    Kratsch, D
    Steiner, G
    DISCRETE MATHEMATICS, 1997, 170 (1-3) : 99 - 106
  • [17] Bounds on the Bend Number of Split and Cocomparability Graphs
    Dibyayan Chakraborty
    Sandip Das
    Joydeep Mukherjee
    Uma Kant Sahoo
    Theory of Computing Systems, 2019, 63 : 1336 - 1357
  • [18] The Longest Path Problem Is Polynomial on Cocomparability Graphs
    Kyriaki Ioannidou
    Stavros D. Nikolopoulos
    Algorithmica, 2013, 65 : 177 - 205
  • [19] Bounds on the Bend Number of Split and Cocomparability Graphs
    Chakraborty, Dibyayan
    Das, Sandip
    Mukherjee, Joydeep
    Sahoo, Uma Kant
    THEORY OF COMPUTING SYSTEMS, 2019, 63 (06) : 1336 - 1357
  • [20] 1-tough cocomparability graphs are hamiltonian
    Discrete Math, 1-3 (99-106):
12345