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 条
  • [41] Unique irredundance, domination and independent domination in graphs
    Fischermann, M
    Volkmann, L
    Zverovich, I
    DISCRETE MATHEMATICS, 2005, 305 (1-3) : 190 - 200
  • [42] On Secure Domination in Graphs
    Merouane, Houcine Boumediene
    Chellali, Mustapha
    INFORMATION PROCESSING LETTERS, 2015, 115 (10) : 786 - 790
  • [43] On the signed domination in graphs
    Matousek, J
    COMBINATORICA, 2000, 20 (01) : 103 - 108
  • [44] Domination in Circulant Graphs
    Rad, Nader Jafari
    ANALELE STIINTIFICE ALE UNIVERSITATII OVIDIUS CONSTANTA-SERIA MATEMATICA, 2009, 17 (01): : 169 - 176
  • [45] Partial Domination in Graphs
    Angsuman Das
    Iranian Journal of Science and Technology, Transactions A: Science, 2019, 43 : 1713 - 1718
  • [46] Domination index in graphs
    Nair, Kavya. R.
    Sunitha, M. S.
    ASIAN-EUROPEAN JOURNAL OF MATHEMATICS, 2024, 17 (10)
  • [47] Domination in signed graphs
    Jeyalakshmi, P.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (01)
  • [48] Theory of Domination in Graphs
    Sinha, Deepa
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2015, 18 (06): : 903 - +
  • [49] Rainbow domination in graphs
    Bresar, Bostjan
    Henning, Michael A.
    Rall, Douglas F.
    TAIWANESE JOURNAL OF MATHEMATICS, 2008, 12 (01): : 213 - 225
  • [50] Structural domination of graphs
    Bascó, G
    Tuza, Z
    ARS COMBINATORIA, 2002, 63 : 235 - 256
12345