The 0-1 inverse maximum independent set problem on forests and unicyclic graphs

被引：1
|
作者：
Liu, Shuaifu [1 ]
Zhang, Zhao [2 ]
机构：
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
[2] Zhejiang Normal Univ, Coll Math Phys & Informat Engn, Jinhua 321004, Zhejiang, Peoples R China
来源：
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS | 2016年 / 8卷 / 02期
关键词：
Inverse combinatorial optimization; independent set; algorithm;
D O I：
10.1142/S1793830916500191
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
Given a graph G and an independent set S of G, the 0-1 inverse maximum independent set problem (IMIS0,1) is to delete as few vertices as possible such that S becomes a maximum independent set of G. It is known that IMIS0,1 is NP-hard even when the given independent set has a bounded size. In this paper, we present linear-time algorithms for IMIS0,1 on forests and unicyclic graphs.
引用
收藏
页数：8
相关论文
共 50 条
  • [1] The 0-1 inverse maximum stable set problem
    Chung, Yerim
    Demange, Marc
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (13) : 2501 - 2516
  • [2] Maximum 0-1 timed matching on temporal graphs
    Mandal, Subhrangsu
    Gupta, Arobinda
    DISCRETE APPLIED MATHEMATICS, 2022, 319 : 310 - 326
  • [3] On the maximum independent set problem in subclasses of subcubic graphs
    Lozin, Vadim
    Monnot, Jerome
    Ries, Bernard
    JOURNAL OF DISCRETE ALGORITHMS, 2015, 31 : 104 - 112
  • [4] The Maximum Independent Set Problem in Subclasses of Subcubic Graphs
    Brause, Christoph
    Ngoc Chi Le
    Schiermeyer, Ingo
    DISCRETE MATHEMATICS, 2015, 338 (10) : 1766 - 1778
  • [5] On the independent set problem in random graphs
    Song, Yinglei
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2015, 92 (11) : 2233 - 2242
  • [6] Maximum independent set and maximum clique algorithms for overlap graphs
    Cenek, E
    Stewart, L
    DISCRETE APPLIED MATHEMATICS, 2003, 131 (01) : 77 - 91
  • [7] Graphs Without Large Apples and the Maximum Weight Independent Set Problem
    Vadim V. Lozin
    Martin Milanič
    Christopher Purcell
    Graphs and Combinatorics, 2014, 30 : 395 - 410
  • [8] Graphs Without Large Apples and the Maximum Weight Independent Set Problem
    Lozin, Vadim V.
    Milanic, Martin
    Purcell, Christopher
    GRAPHS AND COMBINATORICS, 2014, 30 (02) : 395 - 410
  • [9] Maximum weight k-independent set problem on permutation graphs
    Saha, A
    Pal, M
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (12) : 1477 - 1487
  • [10] ON THE MAXIMUM WEIGHT INDEPENDENT SET PROBLEM IN GRAPHS WITHOUT INDUCED CYCLES OF LENGTH AT LEAST FIVE
    Chudnovsky, Maria
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Thomasse, Stephan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (02) : 1472 - 1483
12345