Publication detailsDabrowski, Konrad K., Lozin, Vadim V., de Werra, Dominique & Zamaraev, Viktor (2016). Combinatorics and Algorithms for Augmenting Graphs. Graphs and Combinatorics 32(4): 1339-1352.
- Publication type: Journal Article
- ISSN/ISBN: 0911-0119 (print), 1435-5914 (electronic)
- DOI: 10.1007/s00373-015-1660-0
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.