Approximability of the vertex cover problem in power-law graphs
From MaRDI portal
Publication:385960
DOI10.1016/j.tcs.2013.11.004zbMath1277.68298arXiv1204.0982OpenAlexW2015692161MaRDI QIDQ385960
Mathias Hauptmann, Mikael Gast
Publication date: 13 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.0982
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items (3)
Minimum vertex cover in generalized random graphs with power law degree distribution ⋮ Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry ⋮ Inapproximability of dominating set on power law graphs
Cites Work
- Unnamed Item
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- Optimization, approximation, and complexity classes
- Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
- Popularity based random graph models leading to a scale-free degree sequence
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the hardness of optimization in power-law graphs
- On certain connectivity properties of the internet topology
- A Random Graph Model for Power Law Graphs
- On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs
- Emergence of Scaling in Random Networks
- A random graph model for massive graphs
- Assessing Significance of Connectivity and Conservation in Protein Interaction Networks
- Vertex packings: Structural properties and algorithms
- A general model of web graphs
- Reducibility among Combinatorial Problems
This page was built for publication: Approximability of the vertex cover problem in power-law graphs
