ON SEQUENTIAL HEURISTIC METHODS FOR THE MAXIMUM INDEPENDENT SET PROBLEM

被引：0

作者：

Le, Ngoc C. ^{[1
,2
]}

Brause, Christoph ^{[1
]}

Schiermeyer, Ingo ^{[1
]}

机构：

[1] Tech Univ Bergakad Freiberg, Fac Math & Comp Sci, Freiberg, Germany

[2] Hanoi Univ Sci & Technol, Sch Appl Math & Informat, Hanoi, Vietnam

来源：

DISCUSSIONES MATHEMATICAE GRAPH THEORY | 2017年 / 37卷 / 02期

关键词：

maximum independent set; heuristic; MIN; MAX; VO; vertex ordering; STABILITY NUMBER; LOWER BOUNDS; GRAPHS; ALGORITHM; TERMS;

D O I：

10.7151/dmgt.1965

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6], are revisited. We combine Algorithm MIN with the alpha-redundant vertex technique [3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4, 14] is verified and performance of the algorithms on some special graphs is considered.

引用

页码：402 / 413

页数：12

共 50 条

[1] Solving the Set Packing Problem via a Maximum Weighted Independent Set Heuristic
Li, Ruizhi
Wang, Yupan
Hu, Shuli
Jiang, Jianhua
Ouyang, Dantong
Yin, Minghao
MATHEMATICAL PROBLEMS IN ENGINEERING, 2020, 2020
[2] A Heuristic for the Maximum Independent Set Problem Based on Optimization of a Quadratic Over a Sphere
Stanislav Busygin
Sergiy Butenko
Panos M. Pardalos
Journal of Combinatorial Optimization, 2002, 6 : 287 - 297
[3] A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
Busygin, S
Butenko, S
Pardalos, PM
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2002, 6 (03) : 287 - 297
[4] A hybrid iterated local search heuristic for the maximum weight independent set problem
Bruno Nogueira
Rian G. S. Pinheiro
Anand Subramanian
Optimization Letters, 2018, 12 : 567 - 583
[5] A hybrid iterated local search heuristic for the maximum weight independent set problem
Nogueira, Bruno
Pinheiro, Rian G. S.
Subramanian, Anand
OPTIMIZATION LETTERS, 2018, 12 (03) : 567 - 583
[6] HEURISTIC ALGORITHM FOR FINDING THE MAXIMUM INDEPENDENT SET
Plotnikov, A. D.
CYBERNETICS AND SYSTEMS ANALYSIS, 2012, 48 (05) : 673 - 680
[7] SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE MAXIMUM-WEIGHT INDEPENDENT SET PROBLEM ON PERMUTATION GRAPHS
YU, MS
TSENG, LY
CHANG, SJ
INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 7 - 11
[8] The maximum independent set problem in planar graphs
Alekseev, Vladimir E.
Lozin, Vadim
Malyshev, Dmitriy
Milanic, Martin
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2008, PROCEEDINGS, 2008, 5162 : 96 - +
[9] Sticker model for maximum clique problem and maximum independent set
Fan Y.-K.
Qiang X.-L.
Xu J.
Jisuanji Xuebao/Chinese Journal of Computers, 2010, 33 (02): : 305 - 310
[10] On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree
Ngoc C. Lê
Trung Tran
Acta Mathematica Vietnamica, 2020, 45 : 463 - 475

← 1 2 3 4 5 →