Konrad K. Dabrowski
Combinatorics and Algorithms for Augmenting Graphs
Dabrowski, Konrad K.; Lozin, Vadim V.; de Werra, Dominique; Zamaraev, Viktor
Authors
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.
Published Journal Article (Final published version)
(545 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
Final published version
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search