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 条
  • [21] ON SEQUENTIAL HEURISTIC METHODS FOR THE MAXIMUM INDEPENDENT SET PROBLEM
    Le, Ngoc C.
    Brause, Christoph
    Schiermeyer, Ingo
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2017, 37 (02) : 402 - 413
  • [22] Problem reduction heuristic for the 0-1 multidimensional knapsack problem
    Hill, Raymond R.
    Cho, Yong Kun
    Moore, James T.
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (01) : 19 - 26
  • [23] On disjoint maximum and maximal independent sets in graphs and inverse independence number
    Kaci, Fatma
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2023, 15 (08)
  • [24] Robust maximum weighted independent-set problems on interval graphs
    Fabrice Talla Nobibon
    Roel Leus
    Optimization Letters, 2014, 8 : 227 - 235
  • [25] On maximum independent set of categorical product and ultimate categorical ratios of graphs
    Hon, Wing-Kai
    Kloks, Ton
    Liu, Ching-Hao
    Liu, Hsiang-Hsuan
    Poon, Sheung-Hung
    Wang, Yue-Li
    THEORETICAL COMPUTER SCIENCE, 2015, 588 : 81 - 95
  • [26] Robust maximum weighted independent-set problems on interval graphs
    Nobibon, Fabrice Talla
    Leus, Roel
    OPTIMIZATION LETTERS, 2014, 8 (01) : 227 - 235
  • [27] A hybrid heuristic for the 0-1 Knapsack Sharing Problem
    Haddar, Boukthir
    Khemakhem, Mahdi
    Hanafi, Said
    Wilbaut, Christophe
    EXPERT SYSTEMS WITH APPLICATIONS, 2015, 42 (10) : 4653 - 4666
  • [28] Discrete cuckoo search for 0-1 knapsack problem
    Ouaarab, Aziz
    INTERNATIONAL JOURNAL OF DATA MINING MODELLING AND MANAGEMENT, 2024, 16 (04)
  • [29] A new class of hard problem instances for the 0-1 knapsack problem
    Jooken, Jorik
    Leyman, Pieter
    De Causmaecker, Patrick
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 301 (03) : 841 - 854
  • [30] A (DELTA/2)-APPROXIMATION ALGORITHM FOR THE MAXIMUM INDEPENDENT SET PROBLEM
    PASCHOS, VT
    INFORMATION PROCESSING LETTERS, 1992, 44 (01) : 11 - 13
12345