Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

DOI10.1016/j.ipl.2003.11.002zbMath1176.05076OpenAlexW2061360377MaRDI QIDQ1029074

Van Bang Le, H. N. de Ridder, Andreas Brandstädt

Publication date: 9 July 2009

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2003.11.002

zbMATH Keywords

graph algorithmsmodular decompositionefficient graph algorithmsmaximum weight stable set problem on graphsrobust graph algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (7)

Unnamed Item ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Recent developments on graphs of bounded clique-width ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structure and stability number of chair-, co-P- and gem-free graphs revisited
• 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é
• Complement reducible graphs
• Stability number of bull- and chair-free graphs
• Modular decomposition and transitive orientation
• Stability number of bull- and chair-free graphs revisited
• Conic reduction of graphs for the stable set problem
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• A Linear Recognition Algorithm for Cographs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Graph Classes: A Survey
• Polynomial algorithm for finding the largest independent sets in graphs without forks

This page was built for publication: Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes