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

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

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)

• Can we locally compute sparse connected subgraphs?
• Introduction to testing graph properties
• Approximating Average Parameters of Graphs
• The program of the mini-workshop
• Introduction to testing graph properties
• Sublinear graph approximation algorithms
• On constant time approximation of parameters of bounded degree graphs
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms
• scientific article; zbMATH DE number 6784973 (Why is no real title available?)
• A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
• Space-efficient local computation algorithms
• Approximating the minimum vertex cover in sublinear time and a connection to distributed 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)