Shortest‐path metric approximation for random subgraphs

DOI10.1002/RSA.20150zbMath1113.05093OpenAlexW4248588986MaRDI QIDQ3419615

Jan Vondrák

Publication date: 7 February 2007

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20150

zbMATH Keywords

random graphsapproximation algorithmsspanners

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (2)

Set selection under explorable stochastic uncertainty via covering techniques ⋮ Stochastic minimum vertex cover in general graphs: a \(3/2\)-approximation

Cites Work

• Unnamed Item
• Unnamed Item

This page was built for publication: Shortest‐path metric approximation for random subgraphs