Constant-time local computation algorithms

DOI10.1007/s00224-017-9788-3zbMath1390.68765OpenAlexW3021670975MaRDI QIDQ1743110

Boaz Patt-Shamir, Yishay Mansour, Shai Vardi

Publication date: 12 April 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9788-3

zbMATH Keywords

approximation algorithmssublinear algorithmslocal computation algorithmsmaximal weight forest

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items (1)

Average Sensitivity of Graph Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• Non-local probes do not help with many graph problems
• New techniques and tighter bounds for local computation algorithms
• Converting Online Algorithms to Local Computation Algorithms
• A Local Computation Approximation Scheme to Maximum Matching
• Survey of local algorithms
• Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
• Lower bounds for local approximation
• Distributed Approximate Matching
• The price of being near-sighted
• Deterministic coin tossing with applications to optimal parallel list ranking
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• What Can be Computed Locally?
• Some simple distributed algorithms for sparse networks
• Distributed Weighted Matching
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history

This page was built for publication: Constant-time local computation algorithms