Augmenting graphs for independent sets

DOI10.1016/J.DAM.2003.09.003MaRDI QIDQ705491zbMATH OpenOpenAlexFDO

Authors V. E. Alekseev, Vadim 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

Independent setAugmenting graphPolynomial algorithm

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

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

Cited in

(18)

• On independent vertex sets in subclasses of apple-free graphs
• Extending the MAX algorithm for maximum independent set
• scientific article; zbMATH DE number 2246590 (Why is no real title available?)
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• On finding augmenting graphs
• Augmenting chains in graphs without a skew star.
• From matchings to independent sets
• Combinatorics and algorithms for augmenting graphs
• Independent sets in graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Stable sets in two subclasses of banner-free graphs
• Finding augmenting chains in extensions of claw-free graphs
• Parameterized algorithms for the independent set problem in some hereditary graph classes
• scientific article; zbMATH DE number 20270 (Why is no real title available?)
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On sequential heuristic methods for the maximum independent set problem
• Minimum cost and list homomorphisms to semicomplete digraphs

This page was built for publication: Augmenting graphs for independent sets

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