EXTENDING THE MAX ALGORITHM FOR MAXIMUM INDEPENDENT SET

被引：3
|
作者：
Le, Ngoc C. [1 ]
Brause, Christoph [2 ]
Schiermeyer, Ingo [2 ]
机构：
[1] Hanoi Univ Sci & Technol, Sch Appl Math & Informat, Hanoi, Vietnam
[2] Tech Univ Bergakad Freiberg, Fac Math & Comp Sci, Freiberg, Germany
来源：
DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2015年 / 35卷 / 02期
关键词：
maximum independent set; stable set; stability number; independence number; reduction; graph transformation; MAX Algorithm; MIN Algorithm; Vertex Order Algorithm; ALPHA-REDUNDANT VERTICES; LOWER BOUNDS; STABILITY; GRAPHS; NUMBER; TERMS; (P-6;
D O I：
10.7151/dmgt.1811
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The maximum independent set problem is an NP-hard problem. In this paper, we consider Algorithm MAX, which is a polynomial time algorithm for finding a maximal independent set in a graph G. We present a set of forbidden induced subgraphs such that Algorithm MAX always results in finding a maximum independent set of G. We also describe two modifications of Algorithm MAX and sets of forbidden induced subgraphs for the new algorithms.
引用
收藏
页码：365 / 386
页数：22
相关论文
共 50 条
  • [1] Algorithm for finding maximum independent set
    Olemskoy, I., V
    Firyulina, O. S.
    VESTNIK SANKT-PETERBURGSKOGO UNIVERSITETA SERIYA 10 PRIKLADNAYA MATEMATIKA INFORMATIKA PROTSESSY UPRAVLENIYA, 2014, 10 (01): : 79 - 89
  • [2] A genetic algorithm for maximum independent set problems
    Liu, XZ
    Sakamoto, A
    Shimamoto, T
    INFORMATION INTELLIGENCE AND SYSTEMS, VOLS 1-4, 1996, : 1916 - 1921
  • [3] Maximum Independent Set Algorithm for Hypergraph Data
    Xu L.-T.
    Li R.-H.
    Dai Y.-H.
    Wang G.-R.
    Ruan Jian Xue Bao/Journal of Software, 2024, 35 (06): : 2999 - 3012
  • [4] HEURISTIC ALGORITHM FOR FINDING THE MAXIMUM INDEPENDENT SET
    Plotnikov, A. D.
    CYBERNETICS AND SYSTEMS ANALYSIS, 2012, 48 (05) : 673 - 680
  • [5] A polytime preprocess algorithm for the maximum independent set problem
    Kroger, Samuel
    Validi, Hamidreza
    Hicks, Illya V.
    OPTIMIZATION LETTERS, 2024, 18 (02) : 651 - 661
  • [6] An elitist genetic algorithm for the maximum independent set problem
    Taranenko, A
    Vesel, A
    ITI 2001: PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY INTERFACES, 2001, : 373 - 378
  • [7] A Modified Genetic Algorithm for Maximum Independent Set Problems
    刘兴钊
    坂本明雄
    岛本隆
    Journal of Harbin Institute of Technology, 1999, (02) : 5 - 10
  • [8] Solution to The Maximum Independent Set Problem with Genetic Algorithm
    Gencer, Mehmet
    Berberler, Murat Ersen
    2017 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND ENGINEERING (UBMK), 2017, : 734 - 738
  • [9] A polytime preprocess algorithm for the maximum independent set problem
    Samuel Kroger
    Hamidreza Validi
    Illya V. Hicks
    Optimization Letters, 2024, 18 : 651 - 661
  • [10] A greedy approach to solve maximum independent set problem: Differential Malatya independent set algorithm
    Oztemiz, Furkan
    ENGINEERING SCIENCE AND TECHNOLOGY-AN INTERNATIONAL JOURNAL-JESTECH, 2025, 63
12345