Vertex Cover, Dominating Set and My Encounters with Parameterized Complexity and Mike Fellows.
Venkatesh RamanPublished in: The Multivariate Algorithmic Revolution and Beyond (2012)
Keyphrases
- vertex cover
- dominating set
- parameterized complexity
- approximation algorithms
- facility location problem
- np hard
- fixed parameter tractable
- global constraints
- precedence constraints
- worst case
- partial order
- special case
- minimum cost
- planar graphs
- scheduling problem
- optimality criterion
- polynomial time approximation
- branch and bound algorithm
- integer programming
- lagrangian relaxation
- facility location
- upper bound