Maximum Weight Independent Sets in (S1,1,3, bull)-free Graphs

被引：3

作者：

Karthick, T. ^{[1
]}

Maffray, Frederic ^{[2
]}

机构：

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

[2] Univ Grenoble Alpes, CNRS, Laboratoire G SCOP, Grenoble, France

来源：

COMPUTING AND COMBINATORICS, COCOON 2016 | 2016年 / 9797卷

关键词：

Graph algorithms; Weighted independent set; Modular decomposition; Claw-free graph; Fork-free graph; Bull-free graph; HOLE-FREE; ALGORITHM; DART;

D O I：

10.1007/978-3-319-42634-1_31

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise non-adjacent vertices of maximum total weight. The MWIS problem is well known to be NP-complete in general, even under substantial restrictions. The computational complexity of the MWIS problem for S-1,S-1,S-3-free graphs is unknown. In this note, we give a proof for the solvability of the MWIS problem for (S-1,S-1,S-3, bull)-free graphs in polynomial time. Here, an S-1,S-1,S-3 is the graph with vertices v(1), v(2), v(3), v(4), v(5), v(6) and edges v(1)v(2,) v(2)v(3), v(3)v(4), v(4)v(5), v(4)v(6), and the bull is the graph with vertices v(1), v(2), v(3), v(4), v(5) and edges v(1)v(2), v(2)v(3), v(3)v(4), v(2)v(5), v(3)v(5).

引用

页码：385 / 392

页数：8

共 34 条

[1]

Alekseev VE, 2008, LECT NOTES COMPUT SC, V5162, P96

[2]

Alekseev Vladimir E., 1982, Combinatorial-Algebraic Methods in Applied Mathematics, P3

[3]

Arora S, 2009, COMPUTATIONAL COMPLEXITY: A MODERN APPROACH, P1, DOI 10.1017/CBO9780511804090

[4] Maximum weight independent sets in hole- and dart-free graphs [J].

Basavaraju, M. ;

Chandran, L. S. ;

Karthick, T. .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (16-17) :2364-2369

[5]

Brandstadt A., 1999, SIAM MONOGRAPHS DISC, V3

[6] 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

[7] Weighted efficient domination in two subclasses of P6-free graphs [J].

Brandstaedt, Andreas ;

Karthick, T. .

DISCRETE APPLIED MATHEMATICS, 2016, 201 :38-46

[8] Maximum Weight Independent Sets in Odd-Hole-Free Graphs Without Dart or Without Bull [J].

Brandstaedt, Andreas ;

Mosca, Raffaele .

GRAPHS AND COMBINATORICS, 2015, 31 (05) :1249-1262

[9] 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

[10] 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

← 1 2 3 4 →