Stable sets in two subclasses of banner-free graphs

DOI10.1016/S0166-218X(03)00395-0zbMath1029.05145OpenAlexW2079563996MaRDI QIDQ1414588

Michael U. Gerber, Alain Hertz, Vadim V. Lozin

Publication date: 4 December 2003

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00395-0

zbMATH Keywords

Stable setPolynomial algorithmAugmenting graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On finding augmenting graphs ⋮ Some new hereditary classes where graph coloring remains NP-hard ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Augmenting graphs for independent sets
• The complexity of generalized clique packing
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Computing independent sets in graphs with large girth
• Stability number of bull- and chair-free graphs
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stable sets in certain \(P_6\)-free graphs
• Robust algorithms for the stable set problem
• Stability in \(P_5\)- and banner-free graphs
• A Linear Recognition Algorithm for Cographs
• On Representatives of Subsets
• Polynomial algorithm for finding the largest independent sets in graphs without forks

This page was built for publication: Stable sets in two subclasses of banner-free graphs