Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Thomas BläsiusPhilipp FischbeckTobias FriedrichMaximilian KatzmannPublished in: STACS (2020)
Keyphrases
- vertex cover
- random graphs
- approximation algorithms
- planar graphs
- undirected graph
- polynomial time approximation
- special case
- graph theoretic
- worst case
- phase transition
- np hard
- precedence constraints
- partial order
- combinatorial optimization
- complex networks
- minimum cost
- computational complexity
- partially ordered
- small world
- approximation ratio
- optimality criterion