On finding augmenting graphs

DOI10.1016/j.dam.2008.03.008zbMath1159.05313OpenAlexW1991000585MaRDI QIDQ955317

Vadim V. Lozin, Martin Milanič

Publication date: 19 November 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.03.008

zbMATH Keywords

independent setpolynomial-time algorithmaugmenting graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

Augmenting approach for some maximum set problems ⋮ Combinatorics and algorithms for augmenting graphs ⋮ The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ From matchings to independent sets ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices

Cites Work

• Unnamed Item
• Augmenting graphs for independent sets
• Finding augmenting chains in extensions of claw-free graphs
• Matching theory
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stable sets in certain \(P_6\)-free graphs
• The independence number of graphs with large odd girth
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• Stability in \(P_5\)- and banner-free graphs
• Augmenting chains in graphs without a skew star.
• TWO THEOREMS IN GRAPH THEORY
• Local transformations of graphs preserving independence number
• On Representatives of Subsets
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Paths, Trees, and Flowers

This page was built for publication: On finding augmenting graphs