Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry

DOI10.1007/S00453-023-01143-XarXiv2010.02787MaRDI QIDQ6066757

Tobias Friedrich, Maximilian Katzmann, Thomas Bläsius

Publication date: 13 December 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.02787

zbMATH Keywords

approximationrandom graphshyperbolic geometryvertex coverefficient algorithm

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry

Cites Work

• Unnamed Item
• Vertex cover meets scheduling
• Minimum vertex cover in generalized random graphs with power law degree distribution
• Approximability of the vertex cover problem in power-law graphs
• On the largest component of a hyperbolic model of complex networks
• The structure and function of networks
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Approximation algorithms for combinatorial problems
• A new upper bound on the game chromatic index of graphs
• Exact algorithms for maximum independent set
• Clustering in a hyperbolic model of complex networks
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Are Stable Instances Easy?
• A better approximation ratio for the vertex cover problem
• Random Hyperbolic Graphs: Degree Sequence and Clustering
• On the Diameter of Hyperbolic Random Graphs
• Metric Embedding, Hyperbolic Space, and Social Networks
• Greed is Good for Deterministic Scale-Free Networks.
• Reducibility among Combinatorial Problems
• True scale-free networks hidden by finite size effects
• Stability and Recovery for Independence Systems
• How rare are power-law networks really?
• A Bound for the Diameter of Random Hyperbolic Graphs
• The diameter of KPKVB random graphs
• On the Method of Typical Bounded Differences
• Success run statistics defined on an urn model
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms
• Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry
• Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
• Pseudorandom sets in Grassmann graph have near-perfect expansion

This page was built for publication: Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry