Minimum vertex cover in generalized random graphs with power law degree distribution
DOI10.1016/j.tcs.2016.08.002zbMath1348.68297OpenAlexW2511587361MaRDI QIDQ306728
Murilo V. G. da Silva, André L. Vignatti
Publication date: 1 September 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.08.002
approximation algorithmsvertex cover problemBritton random graph modelChung-Lu random graph modelgeneralized random graph modelpower-law graphs
Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximability of the vertex cover problem in power-law graphs
- New techniques for approximating optimal substructure problems in power-law graphs
- Inapproximability of dominating set on power law graphs
- Generating simple random graphs with prescribed degree distribution
- The asymptotic number of labeled graphs with given degree sequences
- Connected components in random graphs with given expected degree sequences
- Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- The degree sequence of a scale-free random graph process
- A Random Graph Model for Power Law Graphs
- Random Graphs and Complex Networks
- Emergence of Scaling in Random Networks
- Some problems in the enumeration of labelled graphs
- The Size of the Giant Component of a Random Graph with a Given Degree Sequence
- A critical point for random graphs with a given degree sequence
- The phase transition in inhomogeneous random graphs
- The average distances in random graphs with given expected degrees
- Random Graphs
This page was built for publication: Minimum vertex cover in generalized random graphs with power law degree distribution
