Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.

DOI10.1016/S0020-0190(02)00291-0zbMath1042.68085OpenAlexW2082819223MaRDI QIDQ1853148

Suhail Mahfud, Andreas Brandstädt

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00291-0

zbMATH Keywords

AlgorithmsComputational complexityLinear timeModular decompositionModules in graphsPrime graphsClique width of graphsMaximum Stable SetMonadic Second Order Logic

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Colouring diamond-free graphs ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Bounding clique-width via perfect graphs ⋮ Polynomial-time recognition of clique-width \(\leq 3\) graphs ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ Complexity results for equistable graphs and related classes ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ Two forbidden induced subgraphs and well-quasi-ordering ⋮ The stable set polytope for some extensions of \(P_4\)-free graphs ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Sandwiches missing two ingredients of order four ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Structure and stability number of chair-, co-P- and gem-free graphs revisited ⋮ Unnamed Item ⋮ Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes

Cites Work

• 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
• Modular decomposition and transitive orientation
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• Graph Classes: A Survey
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• Some graph theoretic results associated with Ramsey's theorem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item