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
来源：
DISCRETE APPLIED MATHEMATICS | 2004年 / 145卷 / 01期
关键词：
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 条
[31]   Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth [J].
Dyer, Martin ;
Greenhill, Catherine ;
Mueller, Haiko .
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019), 2019, 11789 :298-310
[32]   Intersections and Unions of Critical Independent Sets in Bipartite Graphs [J].
Levit, Vadim E. ;
Mandrescu, Eugen .
BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2016, 59 (03) :257-260
[33]   On Reconfiguration Graphs of Independent Sets Under Token Sliding [J].
Avis, David ;
Hoang, Duc A. .
GRAPHS AND COMBINATORICS, 2023, 39 (03)
[34]   Maximum Independent Sets in Subcubic Graphs: New Results [J].
Harutyunyan, Ararat ;
Lampis, Michael ;
Lozin, Vadim ;
Monnot, Jerome .
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019), 2019, 11789 :40-52
[35]   Large independent sets in general random intersection graphs [J].
Nikoletseas, S. ;
Raptopoulos, C. ;
Spirakis, P. .
THEORETICAL COMPUTER SCIENCE, 2008, 406 (03) :215-224
[36]   Rainbow independent sets in graphs with maximum degree two [J].
Ma, Yue ;
Hou, Xinmin ;
Gao, Jun ;
Liu, Boyuan ;
Yin, Zhi .
DISCRETE APPLIED MATHEMATICS, 2022, 317 :101-108
[37]   Independent Sets of Random Trees and Sparse Random Graphs [J].
Heilman, Steven .
JOURNAL OF GRAPH THEORY, 2025,
[38]   ODD CYCLE TRANSVERSALS AND INDEPENDENT SETS IN FULLERENE GRAPHS [J].
Faria, Luerbio ;
Klein, Sulamita ;
Stehlik, Matej .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (03) :1458-1469
[39]   An upper bound for the number of independent sets in regular graphs [J].
Galvin, David .
DISCRETE MATHEMATICS, 2009, 309 (23-24) :6635-6640
[40]   Independent Sets of m, n-gonal Graphs [J].
Khantavchai, A. ;
Jiarasuksakun, T. .
THAI JOURNAL OF MATHEMATICS, 2016, 14 (01) :1-12
12345