Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs

DOI10.1016/S0020-0190(96)00197-4zbMath1337.68136MaRDI QIDQ290201

Raffaele Mosca

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitystable setcombinatorial problemspolynomial algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (25)

Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ A note on the computational complexity of graph vertex partition ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ Struction revisited ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ A note on \(\alpha\)-redundant vertices in graphs ⋮ Stability number in subclasses of \(P_5\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Augmenting graphs for independent sets ⋮ Augmenting chains in graphs without a skew star. ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ Finding augmenting chains in extensions of claw-free graphs ⋮ Some results on graphs without long induced paths ⋮ Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ On the stable set problem in special \(P_{5}\)-free graphs ⋮ On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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é
• Dominating cliques in \(P_ 5\)-free graphs
• Stability number of bull- and chair-free graphs
• Geometric algorithms and combinatorial optimization
• Some simplified NP-complete graph problems
• The complexity of comparability graph recognition and coloring
• New classes of Berge perfect graphs
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• A Graph-Theoretic Approach to a Class of Integer-Programming Problems

This page was built for publication: Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs