On finding augmenting graphs

作     者：Lozin, Vadim V. Milanic, Martin 

作者机构：Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Bielefeld Fac Technol AG Genome Informat D-4800 Bielefeld Germany 

出 版 物：《DISCRETE APPLIED MATHEMATICS》 (离散应用数学)

年 卷 期：2008年第156卷第13期

页      面：2517-2529页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：independent set augmenting graph polynomial-time algorithm 

摘      要：Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, tile approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce tile notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs. (c) 2008 Elsevier B.V. All rights reserved.