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 条
  • [1] Independent sets in graphs without subtrees with many leaves
    Alekseev V.E.
    Zakharova D.V.
    Journal of Applied and Industrial Mathematics, 2016, 10 (1) : 1 - 6
  • [2] Counting independent sets in tricyclic graphs
    Poureidi, Abolfazl
    DISCRETE APPLIED MATHEMATICS, 2023, 331 : 138 - 146
  • [3] Counting independent sets in cocomparability graphs
    Dyer, Martin
    Mueller, Haiko
    INFORMATION PROCESSING LETTERS, 2019, 144 : 31 - 36
  • [4] The Number of Independent Sets In Hexagonal Graphs
    Deng, Zhun
    Ding, Jie
    Heal, Kathryn
    Tarokh, Vahid
    2017 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2017, : 2910 - 2914
  • [5] On disjoint maximal independent sets in graphs
    Schaudt, Oliver
    INFORMATION PROCESSING LETTERS, 2015, 115 (01) : 23 - 27
  • [6] ON THE NUMBER OF MAXIMUM INDEPENDENT SETS OF GRAPHS
    Derikvand, T.
    Oboudi, M. R.
    TRANSACTIONS ON COMBINATORICS, 2014, 3 (01) : 29 - 36
  • [7] On finding augmenting graphs
    Lozin, Vadim V.
    Milanic, Martin
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (13) : 2517 - 2529
  • [8] Counting independent sets in Riordan graphs
    Cheon, Gi-Sang
    Jung, Ji-Hwan
    Kang, Bumtle
    Kim, Hana
    Kim, Suh-Ryung
    Kitaev, Sergey
    Mojallal, Seyed Ahmad
    DISCRETE MATHEMATICS, 2020, 343 (11)
  • [9] The number of independent sets of tricyclic graphs
    Zhu, Zhongxun
    Yu, Qigang
    APPLIED MATHEMATICS LETTERS, 2012, 25 (10) : 1327 - 1334
  • [10] The number of maximum independent sets in graphs
    Jou, MJ
    Chang, GJ
    TAIWANESE JOURNAL OF MATHEMATICS, 2000, 4 (04): : 685 - 695
12345