Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Combinatorics and algorithms for augmenting graphs.

Dabrowski, Konrad K. and Lozin, Vadim V. and de Werra, Dominique and Zamaraev, Viktor (2016) 'Combinatorics and algorithms for augmenting graphs.', Graphs and combinatorics., 32 (4). pp. 1339-1352.

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.

Item Type:Article
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Advance online version)
(549Kb)
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF (Final published version)
(532Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00373-015-1660-0
Publisher statement: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.
Date accepted:19 November 2015
Date deposited:18 May 2016
Date of first online publication:23 December 2015
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar