Distance Approximation in Bounded-Degree and General Sparse Graphs

DOI10.1007/11830924_43zbMATH Open1155.68582OpenAlexW1525849820MaRDI QIDQ3595402FDOQ3595402

Authors: Sharon Marko, Dana Ron 

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

Recommendations

• Approximating the distance to properties in bounded-degree and general sparse graphs
• Property testing in bounded degree graphs
• scientific article; zbMATH DE number 1241385
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• scientific article; zbMATH DE number 1559556

Mathematics Subject Classification ID

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

Cited In (13)

• Title not available (Why is that?)
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• The program of the mini-workshop
• Space-efficient local computation algorithms
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Introduction to testing graph properties
• Introduction to testing graph properties
• Can we locally compute sparse connected subgraphs?
• Sublinear graph approximation algorithms
• Approximating Average Parameters of Graphs
• Approximating the distance to properties in bounded-degree and general sparse graphs
• On constant time approximation of parameters of bounded degree graphs
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

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

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