Local computation algorithms for graphs of non-constant degrees

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

zbMATH Keywords

maximum matchingrandomized algorithmsmaximal independent setlocal computation algorithms

Mathematics Subject Classification ID

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