Computational complexity of minimum P4 vertex cover problem for regular and K1, 4-free graphs.
N. Safina DeviAniket C. ManeSounaka MishraPublished in: Discret. Appl. Math. (2015)
Keyphrases
- vertex cover
- planar graphs
- computational complexity
- approximation algorithms
- np hard
- special case
- minimum cost
- partial order
- spanning tree
- constant factor
- undirected graph
- np complete
- polynomial time approximation
- optimality criterion
- graph theory
- worst case
- precedence constraints
- approximation guarantees
- upper bound
- graph structure
- weighted graph
- approximate inference
- minimum spanning tree