Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Thomas BläsiusPhilipp FischbeckTobias FriedrichMaximilian KatzmannPublished in: CoRR (2019)
Keyphrases
- vertex cover
- random graphs
- approximation algorithms
- planar graphs
- undirected graph
- special case
- polynomial time approximation
- graph theoretic
- worst case
- np hard
- optimality criterion
- computational complexity
- precedence constraints
- minimum cost
- phase transition
- partial order
- error bounds
- combinatorial optimization
- small world
- approximation ratio
- constant factor
- greedy algorithm
- objective function