Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry
From MaRDI portal
Publication:6066757
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
Related Items
Cites Work
- 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
- Unnamed Item
