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 条
  • [21] ON THE NUMBER OF MAXIMUM INDEPENDENT SETS IN DOOB GRAPHS
    Krotov, D. S.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2015, 12 : 508 - 512
  • [22] Approximation algorithms for independent sets in map graphs
    Chen, ZZ
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 41 (01): : 20 - 40
  • [23] Combinatorics and Algorithms for Augmenting Graphs
    Dabrowski, Konrad K.
    Lozin, Vadim V.
    de Werra, Dominique
    Zamaraev, Viktor
    GRAPHS AND COMBINATORICS, 2016, 32 (04) : 1339 - 1352
  • [24] Independent sets in graphs with an excluded clique minor
    Wood, David R.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2007, 9 (01): : 171 - 175
  • [25] CONNECTED GRAPHS WITH A LARGE NUMBER OF INDEPENDENT SETS
    Jou, Min-Jen
    TAIWANESE JOURNAL OF MATHEMATICS, 2013, 17 (06): : 2011 - 2017
  • [26] On Maximal Det-Independent (Res-Independent) Sets in Graphs
    Muhammad Zill-E-Shams
    Usman Salman
    Graphs and Combinatorics, 2022, 38
  • [27] On Maximal Det-Independent (Res-Independent) Sets in Graphs
    Zill-E-Shams
    Salman, Muhammad
    Ali, Usman
    GRAPHS AND COMBINATORICS, 2022, 38 (02)
  • [28] On Reconfiguration Graphs of Independent Sets Under Token Sliding
    David Avis
    Duc A. Hoang
    Graphs and Combinatorics, 2023, 39
  • [29] The number of independent sets in unicyclic graphs with a given diameter
    Li, Shuchao
    Zhu, Zhongxun
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (07) : 1387 - 1395
  • [30] Intersections and Unions of Critical Independent Sets in Bipartite Graphs
    Levit, Vadim E.
    Mandrescu, Eugen
    BULLETIN MATHEMATIQUE DE LA SOCIETE DES SCIENCES MATHEMATIQUES DE ROUMANIE, 2016, 59 (03): : 257 - 260
12345