TREEWIDTH and PATHWIDTH parameterized by vertex cover
Mathieu ChapelleMathieu LiedloffIoan TodincaYngve VillangerPublished in: CoRR (2013)
Keyphrases
- vertex cover
- bounded treewidth
- approximation algorithms
- np complete
- decision problems
- planar graphs
- conjunctive queries
- np hard
- partial order
- precedence constraints
- search space
- upper bound
- constraint satisfaction problems
- boolean functions
- space complexity
- optimality criterion
- special case
- log likelihood
- polynomial time approximation