On the complexity of local distributed graph problems

DOI10.1145/3055399.3055471zbMath1370.68127arXiv1611.02663OpenAlexW2552279664MaRDI QIDQ4978023

Fabian Kuhn, Mohsen Ghaffari, Yannic Maus

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.02663

zbMATH Keywords

randomizationcompletenesscomplexity classeslocal algorithmsdistributed complexitysequential local algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph algorithms (graph-theoretic aspects) (05C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (24)

Constant space and non-constant time in distributed computing ⋮ Distributed minimum vertex coloring and maximum independent set in chordal graphs ⋮ Network Decomposition and Distributed Derandomization (Invited Paper) ⋮ What can be sampled locally? ⋮ Improved deterministic distributed matching via rounding ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Distributed dominating sets in interval graphs ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ Improved distributed \(\Delta\)-coloring ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Unnamed Item ⋮ Simple and local independent set approximation ⋮ A topological perspective on distributed network algorithms ⋮ Beep-and-sleep: message and energy efficient set cover ⋮ Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Distributed Spanner Approximation ⋮ Linial for lists ⋮ Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: On the complexity of local distributed graph problems