PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs.

David Gamarnik David A. Goldberg Theophane Weber

Published in: SODA (2010)

Keyphrases

independent set
maximum weight
bounded degree
maximum independent set
bipartite graph
minimum weight
partial order
weighted graph
graph theoretic
np hard
approximation algorithms
special case
edge weights
bounded treewidth
multi dimensional
minimum spanning tree