P₅-free augmenting graphs and the maximum stable set problem

DOI10.1016/S0166-218X(03)00394-9MaRDI QIDQ1414587zbMATH OpenFDO

Authors Michael U. Gerber, Alain Hertz, David Schindl

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)00394-9

zbMATH Keywords

Augmenting graphsPolynomial algorithmStable set

Mathematics Subject Classification ID

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

Recommendations

• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs

Cites work

• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• A note on -redundant vertices in graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Augmenting graphs for independent sets
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Modular decomposition and transitive orientation
• On (\(P_{5}\), diamond)-free graphs
• On maximal independent sets of vertices in claw-free graphs
• On the stability number of claw-free \(P_5\)-free and more general graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• 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
• Quasi-threshold graphs
• Some simplified NP-complete graph problems
• Stability in \(P_5\)- and banner-free graphs
• Stable sets in certain \(P_6\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• The Complexity of the Partial Order Dimension Problem
• Trivially perfect graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

Cited in

(16)

• Finding augmenting chains in extensions of claw-free graphs
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Stability in \(P_5\)- and banner-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Gene selection via a new hybrid ant colony optimization algorithm for cancer classification in high-dimensional data
• Stable set and clique polytopes of \((P_{5},\,\mathrm{gem})\)-free graphs
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs
• Counting perfect matchings and the switch chain
• New applications of clique separator decomposition for the maximum weight stable set problem
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs

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

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