𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Dissemination Thresholds in Regular and Irregular Graph Classes

✍ Scribed by I. Rapaport; K. Suchan; I. Todinca; J. Verstraete

Publisher
Springer
Year
2009
Tongue
English
Weight
497 KB
Volume
59
Category
Article
ISSN
0178-4617

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