A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere

被引：31

作者：

Busygin, S ^{[1
]}

Butenko, S

Pardalos, PM

机构：

[1] Contentsoft AG, Munich, Germany

[2] Univ Florida, Dept Ind & Syst Engn, Gainesville, FL 32611 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2002年 / 6卷 / 03期

关键词：

maximum independent set; continuous approach; combinatorial optimization;

D O I：

10.1023/A:1014899909753

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

For a given graph the maximum independent set problem is to find a maximum subset of vertices no two of which are adjacent. We propose a heuristic for the maximum independent set problem which utilizes classical results for the problem of optimization of a quadratic function over a sphere. The efficiency of the approach is confirmed by results of numerical experiments on DIMACS benchmarks.

引用

页码：287 / 297

页数：11

共 22 条

[1]

ABELLO J, 2001, J GLOBAL OPTIMIZATIO, V21

[2]

Abello J., 1999, DIMACS SERIES DISCRE, P119, DOI DOI 10.1007/3-540-68530-8_1

[3]

AVONDOBODENO G, 1962, EC APPL THEORY GRAPH

[4] FINDING A MAXIMUM CLIQUE IN AN ARBITRARY GRAPH [J].

BALAS, E ;

YU, CS .

SIAM JOURNAL ON COMPUTING, 1986, 15 (04) :1054-1068

[5]

Berge C., 1962, THEORY GRAPHS ITS AP

[6]

Bomze IM, 1999, Handbook of Combinatorial Optimization, P1, DOI DOI 10.1007/978-1-4757-3023-4_1

[7]

BUSYGIN S, 2001, QUALEX 2 0 RELEASE N

[8]

DEANGELIS PL, IN PRESS J GLOBAL OP

[9]

Deo N., 1974, GRAPH THEORY APPL EN, V1st

[10] ON STATIONARY VALUES OF A 2ND-DEGREE POLYNOMIAL ON UNIT SPHERE [J].

FORSYTHE, GE ;

GOLUB, GH .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1965, 13 (04) :1050-&

← 1 2 3 →