Local algorithms for sparse spanning graphs

DOI10.1007/s00453-019-00612-6zbMath1435.05190OpenAlexW2966775177MaRDI QIDQ2300722

Reut Levi, Ronitt Rubinfeld, Dana Ron

Publication date: 28 February 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2014/4741/

zbMATH Keywords

property testingsublinear algorithmslocal algorithmsminor-free graphsbounded degree modelsparse spanning subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Average Sensitivity of Graph Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Property-preserving data reconstruction
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Homomorphiesätze für Graphen
• 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
• Noise Tolerance of Expanders and Sublinear Expansion Reconstruction
• Converting Online Algorithms to Local Computation Algorithms
• A Local Computation Approximation Scheme to Maximum Matching
• Local Reconstructors and Tolerant Testers for Connectivity and Diameter
• Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
• Local Algorithms for Sparse Spanning Graphs
• Constructing near spanning trees with few local inspections
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free 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
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Graph spanners
• The Token Distribution Problem
• Locality in Distributed Graph Algorithms
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Distributed Computing: A Locality-Sensitive Approach
• Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
• A Local Algorithm for Constructing Spanners in Minor-Free Graphs
• What Can be Computed Locally?
• A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
• 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
• Flow-Based Algorithms for Local Graph Clustering
• Local Monotonicity Reconstruction
• Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
• Decomposition of Finite Graphs Into Forests
• Distributed algorithms for ultrasparse spanners and linear size skeletons
• Pseudorandom generators without the XOR lemma
• Property testing in bounded degree graphs

This page was built for publication: Local algorithms for sparse spanning graphs