Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Abstract Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of an algorithm (allowing non-optimal outputs) for an improved running time. For the vertex cover problem, there is a gap between …