Local computation algorithms for graphs of non-constant degrees
From MaRDI portal
Publication:524360
DOI10.1007/s00453-016-0126-yzbMath1360.68513arXiv1502.04022OpenAlexW1618811119MaRDI QIDQ524360
Anak Yodpinyanee, Ronitt Rubinfeld, Reut Levi
Publication date: 2 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.04022
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (8)
New techniques and tighter bounds for local computation algorithms ⋮ Can we locally compute sparse connected subgraphs? ⋮ Average Sensitivity of Graph Algorithms ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Property-preserving data reconstruction
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- A fast and simple randomized parallel algorithm for maximal matching
- New techniques and tighter bounds for local computation algorithms
- Pseudorandom generators without the XOR Lemma (extended abstract)
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Noise Tolerance of Expanders and Sublinear Expansion Reconstruction
- Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy
- 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
- Improved Constant-Time Approximation Algorithms for Maximum Matchings and Other Optimization Problems
- The Locality of Distributed Symmetry Breaking
- Distributed Approximate Matching
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An algorithmic approach to the Lovász local lemma. I
- A parallel algorithmic version of the local lemma
- Locality in Distributed Graph Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Flow-Based Algorithms for Local Graph Clustering
- Local Monotonicity Reconstruction
- Online geometric reconstruction
- Algorithms – ESA 2005
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Distributed algorithms for the Lovász local lemma and graph coloring
- Limits of local algorithms over sparse random graphs
This page was built for publication: Local computation algorithms for graphs of non-constant degrees