APPROXIMATING MAXIMUM INDEPENDENT SETS BY EXCLUDING SUBGRAPHS

被引：190

作者：

BOPPANA, R

HALLDORSSON, MM

机构：

[1] NYU,DEPT COMP SCI,NEW YORK,NY 10012

[2] JAPAN ADV INST SCI & TECHNOL,SCH INFORMAT SCI,ISHIKAWA 92312,JAPAN

来源：

BIT | 1992年 / 32卷 / 02期

关键词：

APPROXIMATION ALGORITHMS; INDEPENDENT SETS; GRAPH COLORING;

D O I：

10.1007/BF01994876

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known to O(n/(log n)2). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strong simultaneous performance guarantee for the clique and coloring problems. The framework of subgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.

引用

页码：180 / 196

页数：17

共 22 条

[11]

BOPPANA R, 1990, LECT NOTES COMPUT SC, V447, P13

[12]

CHVATAL V, 1977, SIAM J COMPUT, V6

[13]

ERDOS P, 1967, COLLOQ MATH, V16, P253

[14]

Erdos P., 1935, COMPOS MATH, V2, P463

[15]

FEIGE U, 1991, 32ND P ANN IEEE S F, P2

[16]

Gallai T, 1963, PUBL MATH I HUNG, V8, P165

[17]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[18]

HALLDORSSON MM, 1990, DIMACS9044 TECHN REP

[19]

JOHNSON DS, 1974, 5TH P SE C COMB GRAP, P513

[20] RAMSEY NUMBERS AND AN APPROXIMATION ALGORITHM FOR THE VERTEX COVER PROBLEM [J].

MONIEN, B ;

SPECKENMEYER, E .

ACTA INFORMATICA, 1985, 22 (01) :115-123

← 1 2 3 →