𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum-weight stable sets and safe lower bounds for graph coloring

✍ Scribed by Stephan Held, William Cook, Edward C. Sewell

Book ID
118828922
Publisher
Springer-Verlag
Year
2012
Tongue
English
Weight
252 KB
Volume
4
Category
Article
ISSN
1867-2949

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Maximum Weight Stable Set on graphs with
Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time
✍ Andreas BrandstΓ€dt; Suhail Mahfud πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 112 KB

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 f