Constructing near spanning trees with few local inspections

DOI10.1002/rsa.20652zbMath1359.05022arXiv1502.00413OpenAlexW2963140282MaRDI QIDQ2977565

Guy Moshkovitz, Reut Levi, Dana Ron, Asaf Shapira, Ronitt Rubinfeld

Publication date: 18 April 2017

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.00413

zbMATH Keywords

local algorithmsgraph expansionsparse spanning graph

Mathematics Subject Classification ID

Trees (05C05)

Related Items (3)

Can we locally compute sparse connected subgraphs? ⋮ Unnamed Item ⋮ Local algorithms for sparse spanning graphs

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Property-preserving data reconstruction
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Pseudorandom generators without the XOR Lemma (extended abstract)
• Converting Online Algorithms to Local Computation Algorithms
• Local Reconstructors and Tolerant Testers for Connectivity and Diameter
• Local Algorithms for Sparse Spanning Graphs
• Local Computation of PageRank Contributions
• Bookmark-Coloring Algorithm for Personalized PageRank Computing
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
• A Separator Theorem for Planar Graphs
• Locality in Distributed Graph Algorithms
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• What Can be Computed Locally?
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Local Graph Partitions for Approximation and Testing
• An improved constant-time approximation algorithm for maximum~matchings
• Finding sparse cuts locally using evolving sets
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Local Monotonicity Reconstruction
• Distributed algorithms for ultrasparse spanners and linear size skeletons

This page was built for publication: Constructing near spanning trees with few local inspections