Combinatorics and Algorithms for Augmenting Graphs

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

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: May 18, 2016
• 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
• Public URL: https://durham-repository.worktribe.com/output/1412178