Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs.
Jochen AlberFrederic DornRolf NiedermeierPublished in: Discret. Appl. Math. (2005)
Keyphrases
- vertex cover
- planar graphs
- tree decomposition
- approximation algorithms
- dynamic programming
- polynomial time approximation
- np hard
- worst case
- closed form
- expectation maximization
- optimal solution
- partial order
- maximum likelihood
- linear programming
- special case
- optimality criterion
- search space
- computational complexity