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 条
  • [11] The Maximum Distance-d Independent Set Problem on Unit Disk Graphs
    Jena, Sangram K.
    Jallu, Ramesh K.
    Das, Gautam K.
    Nandy, Subhas C.
    FRONTIERS IN ALGORITHMICS (FAW 2018), 2018, 10823 : 68 - 80
  • [12] Further Improvement on Maximum Independent Set in Degree-4 Graphs
    Xiao, Mingyu
    Nagamochi, Hiroshi
    COMBINATORIAL OPTIMIZATION AND APPLICATIONS, 2011, 6831 : 163 - +
  • [13] Parallel maximum independent set in convex bipartite graphs
    Czumaj, A
    Diks, K
    Przytycka, TM
    INFORMATION PROCESSING LETTERS, 1996, 59 (06) : 289 - 294
  • [14] On the complexity of the independent set problem in triangle graphs
    Orlovich, Yury
    Blazewicz, Jacek
    Dolgui, Alexandre
    Finke, Gerd
    Gordon, Valery
    DISCRETE MATHEMATICS, 2011, 311 (16) : 1670 - 1680
  • [15] A subexponential-time algorithm for the Maximum Independent Set Problem in Pt-free graphs
    Brause, Christoph
    DISCRETE APPLIED MATHEMATICS, 2017, 231 : 113 - 118
  • [16] Solving Robust Variants of the Maximum Weighted Independent Set Problem on Trees
    Klobucar, Ana
    Manger, Robert
    MATHEMATICS, 2020, 8 (02)
  • [17] An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs
    Neuwohner, Meike
    38TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2021), 2021, 187
  • [18] On the Power of Simple Reductions for the Maximum Independent Set Problem
    Strash, Darren
    COMPUTING AND COMBINATORICS, COCOON 2016, 2016, 9797 : 345 - 356
  • [19] A priori optimization for the probabilistic maximum independent set problem
    Murat, C
    Paschos, VT
    THEORETICAL COMPUTER SCIENCE, 2002, 270 (1-2) : 561 - 590
  • [20] Accelerating Local Search for the Maximum Independent Set Problem
    Dahlum, Jakob
    Lamm, Sebastian
    Sanders, Peter
    Schulz, Christian
    Strash, Darren
    Werneck, Renato F.
    EXPERIMENTAL ALGORITHMS, SEA 2016, 2016, 9685 : 118 - 133
12345