A generalization of Konig-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios

被引：10

作者：

Paschos, VT

Demange, M

机构：

[1] LAMSADE, Université Paris-Dauphine, 75775 Paris Cedex 16, Pl. Marechal De Lattre de Tassigny

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1997年 / 97卷 / 03期

关键词：

complexity; heuristics; integer programming; linear programming; graph theory;

D O I：

10.1016/S0377-2217(96)00271-8

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

We first study a generalization of the Konig-Egervary graphs, the class of the kappa-KE graphs, and propose an exact polynomial time algorithm solving maximum independent set problem in this class. Next, we show how this result can be efficiently used to devise polynomial time approximation algorithms with improved approximation ratios for the maximum independent set problem in general graphs. (C) 1997 Elsevier Science B.V.

引用

页码：580 / 592

页数：13

共 10 条

[1]

ARORA S, 1992, AN S FDN CO, P14

[2]

Berge C, 1973, GRAPHS HYPERGRAPHS

[3]

BOURJOLLY JM, 1984, MATH PROGRAM STUD, V22, P44, DOI 10.1007/BFb0121007

[4] On colouring the nodes of a network [J].