Publication:5090437
From MaRDI portal
DOI10.4230/LIPIcs.ITCS.2019.58MaRDI QIDQ5090437
Anak Yodpinyanee, Ronitt Rubinfeld, Ali Vakilian, Merav Parter
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1902.08266
68Qxx: Theory of computing
Related Items
Average Sensitivity of Graph Algorithms, Light spanners for high dimensional norms via stochastic decompositions, Local algorithms for sparse spanning graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local computation algorithms for graphs of non-constant degrees
- Fast deterministic distributed algorithms for sparse spanners
- On some extremal problems in graph theory
- New techniques and tighter bounds for local computation algorithms
- Constant-Time Local Computation Algorithms
- Spectral sparsification via random spanners
- Converting Online Algorithms to Local Computation Algorithms
- A Local Computation Approximation Scheme to Maximum Matching
- Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
- On the locality of distributed sparse spanner construction
- Local Algorithms for Sparse Spanning Graphs
- Constructing near spanning trees with few local inspections
- A Brief Introduction to Property Testing
- Property testing and its connection to learning and approximation
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Fully dynamic randomized algorithms for graph spanners
- Deterministic Distributed Construction of Linear Stretch Spanners in Polylogarithmic Time
- Local Computation of Nearly Additive Spanners
- Graph spanners
- Routing with Polynomial Communication-Space Trade-Off
- 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
- Tight Bounds for Testing Bipartiteness in General Graphs
- An Optimal Synchronizer for the Hypercube
- A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
- Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
- A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs
- Distributed algorithms for ultrasparse spanners and linear size skeletons
