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

zbMATH Keywords

approximation algorithmsvertex cover problemBritton random graph modelChung-Lu random graph modelgeneralized random graph modelpower-law graphs

Mathematics Subject Classification ID

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

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

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