Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
type: Item
instance of: scholarly article
title: Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
zbMATH Open document ID: 1042.68085
DOI: 10.1016/S0020-0190(02)00291-0
author: Andreas Brandstädt
author: Suhail Mahfud
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: Minty has shown that the Maximum Weight Stable Set (MWS) Problem can be solved in polynomial time when restricted to claw-free graphs. We show that the structure of graphs being both claw-free and co-claw-free is very simple which implies bounded clique width for this graph class. It is known that for graph classes of bounded clique width (assuming that \(k\)-expressions can be determined in linear time), there are linear time algorithms for all problems expressible in Monadic Second Order Logic with quantification only over vertex sets. The problems MWS, Maximum Clique, Domination and Steiner Tree, for example, are expressible in this way. Moreover, we describe the structure of prime graphs being both \(H\)- and \(\overline H\)-free for any four-vertex graph \(H\) and obtain bounded clique width for these graph classes except the \(2K_{2}\)- and \(C_{4}\)-free graphs.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1856484
zbMATH Keywords: Modules in graphs
zbMATH Keywords: Modular decomposition
zbMATH Keywords: Prime graphs
zbMATH Keywords: Clique width of graphs
zbMATH Keywords: Linear time
zbMATH Keywords: Monadic Second Order Logic
zbMATH Keywords: Maximum Stable Set
zbMATH Keywords: Algorithms
zbMATH Keywords: Computational complexity
MaRDI profile type: Publication
cites work: Graph Classes: A Survey
cites work: Complement reducible graphs
cites work: Q3676177
cites work: A Linear Recognition Algorithm for Cographs
cites work: Handle-rewriting hypergraph grammars
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Upper bounds to the clique width of graphs
cites work: Q4954442
cites work: Q5501779
cites work: Q4193514
cites work: Some graph theoretic results associated with Ramsey's theorem
cites work: Some classes of perfectly orderable graphs
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: Modular decomposition and transitive orientation
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Q3683903
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
full work available at URL: s0020-0190(02)00291-0
OpenAlex ID: W2082819223
description: scientific article; zbMATH DE number 1856484