A combinatorial algorithm for minimum weighted colorings of claw-free perfect graphs

被引：6
|
作者：
Li, XL
Zang, WN [1 ]
机构：
[1] Univ Hong Kong, Dept Math, Hong Kong, Hong Kong, Peoples R China
[2] Nankai Univ, Ctr Combinator, Tianjin 300071, Peoples R China
来源：
JOURNAL OF COMBINATORIAL OPTIMIZATION | 2005年 / 9卷 / 04期
基金：
中国国家自然科学基金;
关键词：
perfect graph; graph coloring; network flow; algorithm; complexity;
D O I：
10.1007/s10878-005-1775-y
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
We present an O(n(5)) combinatorial algorithm for the minimum weighted coloring problem on claw-free perfect graphs, which was posed by Hsu and Nemhauser in 1984. Our algorithm heavily relies on the structural descriptions of claw-free perfect graphs given by Chavatal and Sbihi and by Maffray and Reed.
引用
收藏
页码：331 / 347
页数：17
相关论文
共 29 条
  • [1] A Combinatorial Algorithm for Minimum Weighted Colorings of Claw-Free Perfect Graphs
    Xueliang Li
    Wenan Zang
    Journal of Combinatorial Optimization, 2005, 9 : 331 - 347
  • [2] Planarization and Acyclic Colorings of Subcubic Claw-Free Graphs
    Cheng, Christine
    McDermid, Eric
    Suzuki, Ichiro
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2011, 6986 : 107 - 118
  • [3] On the choice number of claw-free perfect graphs
    Gravier, S
    Maffray, F
    DISCRETE MATHEMATICS, 2004, 276 (1-3) : 211 - 218
  • [4] Weighted well-covered claw-free graphs
    Levit, Vadim E.
    Tankus, David
    DISCRETE MATHEMATICS, 2015, 338 (03) : 99 - 106
  • [5] Some classical combinatorial problems on circulant and claw-free graphs: the isomorphism and coloring problems on circulant graphs and the stable set problem on claw-free graphs
    Pietropaoli, Ugo
    4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH, 2009, 7 (03): : 297 - 300
  • [6] Claw-Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ
    King, Andrew D.
    Reed, Bruce A.
    JOURNAL OF GRAPH THEORY, 2015, 78 (03) : 157 - 194
  • [7] Reconfiguring Independent Sets in Claw-Free Graphs
    Bonsma, Paul
    Kaminski, Marcin
    Wrochna, Marcin
    ALGORITHM THEORY - SWAT 2014, 2014, 8503 : 86 - +
  • [8] List monopolar partitions of claw-free graphs
    Churchley, Ross
    Huang, Jing
    DISCRETE MATHEMATICS, 2012, 312 (17) : 2545 - 2549
  • [9] On Coloring a Class of Claw-free Graphs
    Dai, Yingjun
    Foley, Angele M.
    Hoang, Chinh T.
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2019, 346 : 369 - 377
  • [10] Colouring Squares of Claw-free Graphs
    de Verclos, Remi de Joannis
    Kang, Ross J.
    Pastor, Lucas
    CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 2019, 71 (01): : 113 - 129
123