Distance Approximation in Bounded-Degree and General Sparse Graphs

DOI10.1007/11830924_43zbMath1155.68582OpenAlexW1525849820MaRDI QIDQ3595402

Dana Ron, Sharon Marko

Publication date: 28 August 2007

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11830924_43

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (7)

Can we locally compute sparse connected subgraphs? ⋮ Introduction to Testing Graph Properties ⋮ The Program of the Mini-Workshop ⋮ On Constant Time Approximation of Parameters of Bounded Degree Graphs ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ Introduction to Testing Graph Properties ⋮ Unnamed Item

This page was built for publication: Distance Approximation in Bounded-Degree and General Sparse Graphs