Augmenting graphs for independent sets

DOI10.1016/J.DAM.2003.09.003zbMATH Open1056.05131OpenAlexW2059553705MaRDI QIDQ705491FDOQ705491

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

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

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)

Cites Work

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

Cited In (17)

• On independent vertex sets in subclasses of apple-free graphs
• Extending the MAX algorithm for maximum independent set
• Title not available (Why is that?)
• 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
• 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
• Title not available (Why is that?)
• \(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
• Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes

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)