Maximum weight independent sets in hole- and dart-free graphs

被引：11

作者：

Basavaraju, M. ^{[2
]}

Chandran, L. S. ^{[2
]}

Karthick, T. ^{[1
]}

机构：

[1] Indian Stat Inst, Chennai Ctr, Madras 600113, Tamil Nadu, India

[2] Indian Inst Sci, Dept Comp Sci & Automat, Bangalore 560012, Karnataka, India

来源：

DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 16-17期

关键词：

Graph algorithms; Maximum weight independent set problem; Clique separators; Hole-free graphs; CLIQUE SEPARATOR DECOMPOSITION;

D O I：

10.1016/j.dam.2012.06.015

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：2364 / 2369

页数：6

共 21 条

[1]

[Anonymous], 2000, INTRO GRAPH THEORY

[2]

[Anonymous], 2003, COMBINATORIAL OPTIMI

[3]

Berry A., 2011, ATOMIC STRUCTU UNPUB

[4] On the structure and stability number Of P5- and co-chair-free graphs [J].

Brandstädt, A ;

Mosca, R .

DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) :47-65

[5] On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem [J].

Brandstadt, Andreas ;

Hoang, Chinh T. .

THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) :295-306

[6] New applications of clique separator decomposition for the Maximum Weight Stable Set problem [J].

Brandstaedt, Andreas ;

Le, Van Bang ;

Mahfud, Suhail .

THEORETICAL COMPUTER SCIENCE, 2007, 370 (1-3) :229-239

[7] Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences [J].

Brandstaedt, Andreas ;

Giakoumakis, Vassilis ;

Maffray, Frederic .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (4-5) :471-478

[8] Maximum Weight Independent Sets in hole- and co-chair-free graphs [J].

Brandstaedt, Andreas ;

Giakoumakis, Vassilis .

INFORMATION PROCESSING LETTERS, 2012, 112 (03) :67-71

[9] INDEPENDENT SETS OF MAXIMUM WEIGHT IN APPLE-FREE GRAPHS [J].

Brandstaedt, Andreas ;

Lozin, Vadim V. ;

Mosca, Raffaele .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (01) :239-254

[10] The strong perfect graph theorem [J].

Chudnovsky, Maria ;

Robertson, Neil ;

Seymour, Paul ;

Thomas, Robin .

ANNALS OF MATHEMATICS, 2006, 164 (01) :51-229

← 1 2 3 →