The Library
On finding augmenting graphs
Tools
Lozin, Vadim V. and Milanic, Martin (2008) On finding augmenting graphs. In: 5th International Conference on Graphs and Optimization, Leukerbad, Switzerland , Aug, 2006. Published in: Discrete Applied Mathematics, Volume 156 (Number 13). pp. 2517-2529. doi:10.1016/j.dam.2008.03.008 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2008.03.008
Abstract
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.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Graph theory, Set theory, Polynomials | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 6 July 2008 | ||||
Dates: |
|
||||
Volume: | Volume 156 | ||||
Number: | Number 13 | ||||
Number of Pages: | 13 | ||||
Page Range: | pp. 2517-2529 | ||||
DOI: | 10.1016/j.dam.2008.03.008 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Description: | Fifth International Conference on Graphs and Optimization — GOV, 2006 |
||||
Title of Event: | 5th International Conference on Graphs and Optimization | ||||
Type of Event: | Conference | ||||
Location of Event: | Leukerbad, Switzerland | ||||
Date(s) of Event: | Aug, 2006 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |