\(P_{5}\)-free augmenting graphs and the maximum stable set problem

DOI10.1016/S0166-218X(03)00394-9zbMath1029.05144MaRDI QIDQ1414587

David Schindl, Michael U. Gerber, Alain Hertz

Publication date: 4 December 2003

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

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 (8)

The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Gene selection via a new hybrid ant colony optimization algorithm for cancer classification in high-dimensional data ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Counting Perfect Matchings and the Switch Chain

Cites Work

• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Augmenting graphs for independent sets
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Some simplified NP-complete graph problems
• Trivially perfect graphs
• Modular decomposition and transitive orientation
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stable sets in certain \(P_6\)-free graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• Stability in \(P_5\)- and banner-free graphs
• On (\(P_{5}\), diamond)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Quasi-threshold graphs
• The Complexity of the Partial Order Dimension Problem
• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: \(P_{5}\)-free augmenting graphs and the maximum stable set problem