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 条
  • [41] Improved convergent heuristics for the 0-1 multidimensional knapsack problem
    Hanafi, Said
    Wilbaut, Christophe
    ANNALS OF OPERATIONS RESEARCH, 2011, 183 (01) : 125 - 142
  • [42] Variable neighborhood search for the discounted {0-1} knapsack problem
    Wilbaut, Christophe
    Todosijevic, Raca
    Hanafi, Said
    Freville, Arnaud
    APPLIED SOFT COMPUTING, 2022, 131
  • [43] A sufficient condition to extend polynomial results for the Maximum Independent Set Problem
    Mosca, Raffaele
    DISCRETE APPLIED MATHEMATICS, 2017, 216 : 281 - 289
  • [44] Solving the Maximum Independent Set Problem based on Molecule Parallel Supercomputing
    Wang, Zhaocai
    Tan, Jian
    Zhu, Lanwei
    Huang, Wei
    APPLIED MATHEMATICS & INFORMATION SCIENCES, 2014, 8 (05): : 2361 - 2366
  • [45] On independent set in B1-EPG graphs
    Bessy, Stephane
    Bougeret, Marin
    Chaplick, Steven
    Goncalves, Daniel
    Paul, Christophe
    DISCRETE APPLIED MATHEMATICS, 2020, 278 : 62 - 72
  • [46] A sequential algorithm for finding a maximum weight K-independent set on interval graphs
    Pal, M
    Bhattacharjee, GP
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1996, 60 (3-4) : 205 - 214
  • [47] An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs
    Mrinmoy Hota
    Madhumangal Pal
    Tapan K. Pal
    Computational Optimization and Applications, 2001, 18 : 49 - 62
  • [48] An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs
    Hota, M
    Pal, M
    Pal, TK
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 18 (01) : 49 - 62
  • [49] Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
    Gartland, Peter
    Lokshtanov, Daniel
    Masarik, Tomas
    Pilipczuk, Marcin
    Pilipczuk, Michal
    Rzazewski, Pawel
    PROCEEDINGS OF THE 56TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2024, 2024, : 683 - 691
  • [50] On exact solution approaches for bilevel quadratic 0-1 knapsack problem
    Zenarosa, Gabriel Lopez
    Prokopyev, Oleg A.
    Pasiliao, Eduardo L.
    ANNALS OF OPERATIONS RESEARCH, 2021, 298 (1-2) : 555 - 572
12345