Minimum vertex cover in generalized random graphs with power law degree distribution

DOI10.1016/J.TCS.2016.08.002MaRDI QIDQ306728zbMATH OpenOpenAlexFDO

Authors André L. Vignatti, Murilo V. G. da Silva

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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Approximability of the vertex cover problem in power-law graphs
• Vertex Cover Approximations on Random Graphs
• Minimal vertex covers of random trees
• The Probabilistic Minimum Vertex-covering Problem
• Covering minimum spanning trees of random subgraphs
• Covering minimum spanning trees of random subgraphs
• Random graph coverings. I: General theory and graph connectivity
• The minimum generalized vertex cover problem
• Algorithms - ESA 2003
• scientific article; zbMATH DE number 822142

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6469213 (Why is no real title available?)
• A Random Graph Model for Power Law Graphs
• A critical point for random graphs with a given degree sequence
• Approximability of the vertex cover problem in power-law graphs
• Connected components in random graphs with given expected degree sequences
• Emergence of Scaling in Random Networks
• Generating simple random graphs with prescribed degree distribution
• Inapproximability of dominating set on power law graphs
• Introduction to algorithms.
• New techniques for approximating optimal substructure problems in power-law graphs
• Random Graphs
• Random graphs and complex networks. Volume 1
• Some problems in the enumeration of labelled graphs
• Structural sparsity of complex networks: bounded expansion in random models and real-world graphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The asymptotic number of labeled graphs with given degree sequences
• The average distances in random graphs with given expected degrees
• The degree sequence of a scale-free random graph process
• The phase transition in inhomogeneous random graphs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(1)

• Minimal vertex covers of random trees

This page was built for publication: Minimum vertex cover in generalized random graphs with power law degree distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306728)