Approximation algorithms for the weighted independent set problem in sparse graphs.
Akihisa KakoTakao OnoTomio HirataMagnús M. HalldórssonPublished in: Discret. Appl. Math. (2009)
Keyphrases
- approximation algorithms
- independent set
- maximum weight
- np hard
- special case
- maximum independent set
- vertex cover
- worst case
- minimum cost
- primal dual
- undirected graph
- constant factor
- weighted graph
- open shop
- facility location problem
- approximation schemes
- approximation ratio
- minimum weight
- randomized algorithms
- lower bound
- scheduling problem
- weighted sum
- approximation guarantees
- optimal solution
- graph theory
- linear programming
- graph matching
- set cover
- precedence constraints
- partial order
- social networks