Local Reconstructors and Tolerant Testers for Connectivity and Diameter
From MaRDI portal
Publication:2851874
DOI10.1007/978-3-642-40328-6_29zbMath1405.68239arXiv1208.2956OpenAlexW2126000837MaRDI QIDQ2851874
Andrea Campagna, Ronitt Rubinfeld, Alan Guo
Publication date: 4 October 2013
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1208.2956
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Connectivity (05C40) Randomized algorithms (68W20)
Related Items (7)
Sampling Correctors ⋮ Can we locally compute sparse connected subgraphs? ⋮ Approximating the distance to monotonicity of Boolean functions ⋮ Constructing near spanning trees with few local inspections ⋮ Local computation algorithms for graphs of non-constant degrees ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs
This page was built for publication: Local Reconstructors and Tolerant Testers for Connectivity and Diameter