Augmenting graphs for independent sets

DOI10.1016/j.dam.2003.09.003zbMath1056.05131OpenAlexW2059553705MaRDI QIDQ705491

Vladimir E. Alekseev, Vadim V. Lozin

Publication date: 31 January 2005

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

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

zbMATH Keywords

Polynomial algorithmIndependent setAugmenting graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On independent vertex sets in subclasses of apple-free graphs ⋮ From matchings to independent sets ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ Independent sets in graphs ⋮ On finding augmenting graphs ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Minimum cost and list homomorphisms to semicomplete digraphs ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Extending the MAX algorithm for maximum independent set

Cites Work

• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Stability number of bull- and chair-free graphs
• Trivially perfect graphs
• Stable sets in certain \(P_6\)-free graphs
• On semi-\(P_ 4\)-sparse graphs
• Stability in \(P_5\)- and banner-free graphs
• Polynomially solvable cases for the maximum stable set problem
• Quasi-threshold graphs
• TWO THEOREMS IN GRAPH THEORY
• A Linear Recognition Algorithm for Cographs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Paths, Trees, and Flowers