What cannot be computed locally!

DOI10.1145/1011767.1011811zbMath1321.68478OpenAlexW2165441947MaRDI QIDQ5501510

Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

Publication date: 3 August 2015

Published in: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/69768

zbMATH Keywords

lower boundsdominating setlocalitydistributed algorithmsmaximal matchingvertex covermaximal independent setapproximation hardness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (48)

Tight bounds for parallel randomized load balancing ⋮ Membrane computing to enhance time efficiency of minimum dominating set ⋮ Proof labeling schemes ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Can we locally compute sparse connected subgraphs? ⋮ A polynomial-time approximation to a minimum dominating set in a graph ⋮ What can be verified locally? ⋮ Distributed approximation of capacitated dominating sets ⋮ Local MST computation with short advice ⋮ What can be sampled locally? ⋮ Improved deterministic distributed matching via rounding ⋮ Node and edge averaged complexities of local graph problems ⋮ Linear-in-\(\varDelta \) lower bounds in the LOCAL model ⋮ Time-optimal construction of overlay networks ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ Exact distributed sampling ⋮ Distributed verification of minimum spanning trees ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Beeping a maximal independent set ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ A hierarchy of local decision ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Leveraging Linial’s Locality Limit ⋮ An optimal bit complexity randomized distributed MIS algorithm ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ Distributed algorithms for covering, packing and maximum weighted matching ⋮ A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms ⋮ A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Combinatorial algorithms for distributed graph coloring ⋮ What Can be Computed in a Distributed System? ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ A simple local 3-approximation algorithm for vertex cover ⋮ An optimal maximal independent set algorithm for bounded-independence graphs ⋮ Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition ⋮ Compact distributed certification of planar graphs ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Constant-time distributed dominating set approximation ⋮ Empire of colonies: Self-stabilizing and self-organizing distributed algorithm ⋮ Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Dynamic networks of finite state machines ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) ⋮ Distributed backup placement ⋮ Local certification of graphs with bounded genus ⋮ Allowing each node to communicate only once in a distributed system: shared whiteboard models

This page was built for publication: What cannot be computed locally!