A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENT SET

被引：222

作者：

FEO, TA

RESENDE, MGC

SMITH, SH

机构：

[1] OPTIMIZAT ALTERNAT, AUSTIN, TX USA

[2] AT&T BELL LABS, MATH SCI RES CTR, MURRAY HILL, NJ 07974 USA

[3] PURDUE UNIV, KRANNERT SCH MANAGEMENT, W LAFAYETTE, IN 47907 USA

来源：

OPERATIONS RESEARCH | 1994年 / 42卷 / 05期

关键词：

D O I：

10.1287/opre.42.5.860

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

An efficient randomized heuristic for a maximum independent set is presented. The procedure is tested on randomly generated graphs having from 400 to 3,500 vertices and edge probabilities from 0.2 to 0.9. The heuristic can be implemented trivially in parallel and is tested on an MIMD computer with 1, 2, 4 and 8 processors. Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.

引用

页码：860 / 878

页数：19

共 21 条

[1]

Aarts E., 1989, SIMULATED ANNEALING

[2]

AVONDOBODENO G, 1962, EC APPLICATIONS THEO

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

BALAS, E ;

YU, CS .

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

[4] AN ALGORITHM FOR THE MANUFACTURING EQUIPMENT SELECTION PROBLEM [J].

BARD, JF ;

FEO, TA .

IIE TRANSACTIONS, 1991, 23 (01) :83-92

[5] OPERATIONS SEQUENCING IN DISCRETE PARTS MANUFACTURING [J].

BARD, JF ;

FEO, TA .

MANAGEMENT SCIENCE, 1989, 35 (02) :249-255

[6]

Berge C, 1962, THEORY GRAPHS ITS AP

[7]

Bollobas B., 1985, ANN DISCRETE MATH, V28, P47

[8]

Bollobas B, 2001, RANDOM GRAPHS, V73

[9] AN EXACT ALGORITHM FOR THE MAXIMUM CLIQUE PROBLEM [J].

CARRAGHAN, R ;

PARDALOS, PM .

OPERATIONS RESEARCH LETTERS, 1990, 9 (06) :375-382

[10]

DEO N, 1974, GRAPH THEORY APPLICA

← 1 2 3 →