Augmenting graphs for independent sets

被引:19
作者
Alekseev, VE
Lozin, VV
机构
[1] Univ Nizhny Novgorod, Nizhnii Novgorod 603950, Russia
[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA
关键词
independent set; augmenting graph; polynomial algorithm;
D O I
10.1016/j.dam.2003.09.003
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
We consider a general approach to solve the maximum independent set problem based on finding augmenting graphs. For some special classes of graphs, the approach provides polynomial solutions. In this paper we survey classical and recent results on the topic, and describe a new one that generalizes two previously known algorithms. We also discuss some open questions related to the notion of augmenting graphs. (C) 2004 Elsevier B.V. All rights reserved.
引用
收藏
页码:3 / 10
页数:8
相关论文
共 50 条
[41]   Large independent sets in regular graphs of large girth [J].
Lauer, Joseph ;
Wormald, Nicholas .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (06) :999-1009
[42]   Independent point-set dominating sets in graphs [J].
Gupta, Purnima ;
Goyal, Alka ;
Jain, Ranjana .
AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS, 2020, 17 (01) :229-241
[43]   Maximum independent sets in subcubic graphs: New results [J].
Harutyunyan, A. ;
Lampis, M. ;
Lozin, V ;
Monnot, J. .
THEORETICAL COMPUTER SCIENCE, 2020, 846 :14-26
[44]   On the Third Largest Number of Maximal Independent Sets of Graphs [J].
Li, Shuchao ;
Zhang, Huihui .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2016, 39 :S269-S282
[45]   Independent sets in asteroidal triple-free graphs [J].
Broersma, H ;
Kloks, T ;
Kratsch, D ;
Müller, H .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (02) :276-287
[46]   Graphs such that All Minimum Dominating Sets Intersect All Maximally Independent Sets [J].
Johnson, P. D., Jr. ;
Prier, D. R. .
UTILITAS MATHEMATICA, 2012, 89 :211-224
[47]   Minimum connected dominating sets and maximal independent sets in unit disk graphs [J].
Wu, WL ;
Du, HW ;
Jia, XH ;
Li, YS ;
Huang, SCH .
THEORETICAL COMPUTER SCIENCE, 2006, 352 (1-3) :1-7
[48]   LARGE INDEPENDENT SETS IN TRIANGLE-FREE PLANAR GRAPHS [J].
Dvorak, Zdenek ;
Mnich, Matthias .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (02) :1355-1373
[49]   On maximum independent sets in P5-free graphs [J].
Randerath, Bert ;
Schiermeyer, Ingo .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (09) :1041-1044
[50]   On the number of independent sets in cycle-separated tricyclic graphs [J].
Dolati, Ardeshir .
COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2011, 61 (06) :1542-1546