Combinatorics and algorithms for augmenting graphs

DOI10.1007/S00373-015-1660-0MaRDI QIDQ2631076zbMATH OpenOpenAlexDBLPWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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)

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.

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

Cites work

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

Cited in

(9)

• scientific article; zbMATH DE number 2246590 (Why is no real title available?)
• On finding augmenting graphs
• New results on independent sets in extensions of \(2K_2\)-free graphs
• Augmenting chains in graphs without a skew star.
• Finding augmenting chains in extensions of claw-free graphs
• Approximation algorithms for graph augmentation
• scientific article; zbMATH DE number 3878984 (Why is no real title available?)
• 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)