Skip to main content

Research Repository

Advanced Search

Combinatorics and Algorithms for Augmenting Graphs

Dabrowski, Konrad K.; Lozin, Vadim V.; de Werra, Dominique; Zamaraev, Viktor

Combinatorics and Algorithms for Augmenting Graphs Thumbnail


Authors

Konrad K. Dabrowski

Vadim V. Lozin

Dominique de Werra

Viktor Zamaraev



Abstract

The notion of augmenting graphs generalizes Berge’s idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem.

Citation

Dabrowski, K. K., Lozin, V. V., de Werra, D., & Zamaraev, V. (2016). Combinatorics and Algorithms for Augmenting Graphs. Graphs and Combinatorics, 32(4), 1339-1352. https://doi.org/10.1007/s00373-015-1660-0

Journal Article Type Article
Acceptance Date Nov 19, 2015
Online Publication Date Dec 23, 2015
Publication Date Jul 1, 2016
Deposit Date May 17, 2016
Publicly Available Date Mar 28, 2024
Journal Graphs and Combinatorics
Print ISSN 0911-0119
Electronic ISSN 1435-5914
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 32
Issue 4
Pages 1339-1352
DOI https://doi.org/10.1007/s00373-015-1660-0

Files

Published Journal Article (Advance online version) (561 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advance online version This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.





You might also like



Downloadable Citations