Combinatorics and algorithms for augmenting graphs

DOI10.1007/S00373-015-1660-0zbMATH Open1342.05098DBLPjournals/gc/DabrowskiLWZ16arXiv1410.8774OpenAlexW1869170457WikidataQ59474941 ScholiaQ59474941MaRDI QIDQ2631076FDOQ2631076

Authors: Konrad Dabrowski, Vadim Lozin, Dominique De Werra, Victor Zamaraev 

Publication date: 28 July 2016

Published in: Graphs and Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1410.8774

Recommendations

• Augmenting graphs for independent sets
• On finding augmenting graphs
• Combinatorial and graph-theoretical problems and augmenting technique
• Augmenting approach for some maximum set problems
• scientific article; zbMATH DE number 2246590

zbMATH Keywords

independent setpolynomial-time algorithmaugmenting graphgraph class

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Generalized Ramsey theory (05C55) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Matching theory
• Paths, Trees, and Flowers
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Some results on graphs without long induced paths
• On maximal independent sets of vertices in claw-free graphs
• TWO THEOREMS IN GRAPH THEORY
• Title not available (Why is that?)
• On finding augmenting graphs
• Stable sets in certain \(P_6\)-free graphs
• New results on maximum induced matchings in bipartite graphs and beyond
• New sufficient conditions for \(\alpha\)-redundant vertices
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Augmenting chains in graphs without a skew star.

Cited In (9)

• Title not available (Why is that?)
• New results on independent sets in extensions of \(2K_2\)-free graphs
• On finding augmenting graphs
• Augmenting chains in graphs without a skew star.
• Finding augmenting chains in extensions of claw-free graphs
• Approximation algorithms for graph augmentation
• Title not available (Why is that?)
• Augmenting graphs for independent sets
• Combinatorial and graph-theoretical problems and augmenting technique

This page was built for publication: Combinatorics and algorithms for augmenting graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2631076)