Distance Approximation in Bounded-Degree and General Sparse Graphs

DOI10.1007/11830924_43MaRDI QIDQ3595402zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(13)

• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
• scientific article; zbMATH DE number 6784973 (Why is no real title available?)
• 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

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)