Augmenting graphs for independent sets

被引：19

作者：

Alekseev, VE

Lozin, VV

机构：

[1] Univ Nizhny Novgorod, Nizhnii Novgorod 603950, Russia

[2] Rutgers State Univ, RUTCOR, Piscataway, NJ 08854 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2004年 / 145卷 / 01期

关键词：

independent set; augmenting graph; polynomial algorithm;

D O I：

10.1016/j.dam.2003.09.003

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We consider a general approach to solve the maximum independent set problem based on finding augmenting graphs. For some special classes of graphs, the approach provides polynomial solutions. In this paper we survey classical and recent results on the topic, and describe a new one that generalizes two previously known algorithms. We also discuss some open questions related to the notion of augmenting graphs. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：3 / 10

页数：8

共 16 条

[1]

Alekseev V.E., 1982, COMB ALGEBR METHODS, P3

[2]

Alekseev V.E., 1999, DISCRETE ANAL OPER R, V1, P3

[3] 2 THEOREMS IN GRAPH THEORY [J].