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

DOI10.1016/J.TCS.2016.08.002zbMATH Open1348.68297OpenAlexW2511587361MaRDI QIDQ306728FDOQ306728

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

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

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)

Cites Work

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

Cited In (2)

• Minimal vertex covers of random trees
• Efficiently approximating vertex cover on scale-free networks with underlying hyperbolic geometry

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)