Sign in
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
Published in:
Inf. Process. Lett. (2002)
Keyphrases
</>
stable set
maximum weight
independent set
bipartite graph
weighted graph
maximum matching
minimum weight
graph structure
directed graph
association graph
worst case
partial order
edge weights
np hard
spanning tree
shortest path
minimum spanning tree
graph theory
special case
bounded degree