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 条
  • [31] GreedyMAX-type Algorithms for the Maximum Independent Set Problem
    Borowiecki, Piotr
    Goering, Frank
    SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2011, 6543 : 146 - 156
  • [32] Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph
    Agra, Agostinho
    Doostmohammadi, Mandi
    de Souza, Cid C.
    DISCRETE OPTIMIZATION, 2016, 21 : 42 - 70
  • [33] QUASI-POLYNOMIAL TIME APPROXIMATION SCHEMES FOR THE MAXIMUM WEIGHT INDEPENDENT SET PROBLEM IN H-FREE GRAPHS
    Chudnovsky, Maria
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Thomasse, Stephan
    SIAM JOURNAL ON COMPUTING, 2024, 53 (01) : 47 - 86
  • [34] Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
    Chudnovsky, Maria
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Thomasse, Stephan
    PROCEEDINGS OF THE 2020 ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, 2020, : 2260 - 2278
  • [35] Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
    Chudnovsky, Maria
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Thomasse, Stephan
    PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), 2020, : 2260 - 2278
  • [36] Maximum weight independent set for lclaw-free graphs in polynomial time
    Brandstaedt, Andreas
    Mosca, Raffaele
    DISCRETE APPLIED MATHEMATICS, 2018, 237 : 57 - 64
  • [37] An efficient pram algorithm for maximum-weight independent set on permutation graphs
    Saha A.
    Pal M.
    Pal T.K.
    Journal of Applied Mathematics and Computing, 2005, 19 (1-2) : 77 - 92
  • [38] A new Hybrid Heuristic for the 0-1 Knapsack Sharing Problem
    Haddar, Boukthir
    Khemakhem, Mahdi
    Hanafi, Said
    Wilbaut, Christophe
    Chabchoub, Habib
    PROCEEDINGS OF 2013 INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND SYSTEMS MANAGEMENT (IEEE-IESM 2013), 2013, : 12 - 18
  • [39] Expectation analysis for bounding solutions of the 0-1 knapsack problem
    Morales, Fernando A.
    Martinez, Jairo A.
    COMPUTATIONAL & APPLIED MATHEMATICS, 2024, 43 (08):
  • [40] Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem
    Letocart, Lucas
    Nagih, Anass
    Plateau, Gerard
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (01) : 12 - 18
12345