Toward more localized local algorithms: removing assumptions concerning global knowledge
From MaRDI portal
Publication:2441787
DOI10.1007/s00446-012-0174-8zbMath1284.68644arXiv1512.03306OpenAlexW1989134823MaRDI QIDQ2441787
Jean-Sébastien Sereni, Amos Korman, Laurent Viennot
Publication date: 28 March 2014
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1512.03306
Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Distributed algorithms (68W15)
Related Items (9)
The ANTS problem ⋮ Improved deterministic distributed matching via rounding ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Fast rendezvous on a cycle by agents with different speeds
Cites Work
- Local MST computation with short advice
- Communication algorithms with advice
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- An almost optimal algorithm for unbounded searching
- Distributed verification of minimum spanning trees
- Proof labeling schemes
- Distributed computing with advice: information sensitivity of graph coloring
- On the Distributed Complexity of Computing Maximal Matchings
- On the locality of distributed sparse spanner construction
- Distributed Approximate Matching
- Drawing Maps with Advice
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Complexity of network synchronization
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Tight Fault Locality
- Distributed Computing: A Locality-Sensitive Approach
- What Can be Computed Locally?
- On the Complexity of Distributed Network Decomposition
- Label-guided graph exploration by a finite automaton
- Some simple distributed algorithms for sparse networks
- Distributed (δ+1)-coloring in linear (in δ) time
- A new technique for distributed symmetry breaking
- Deterministic distributed vertex coloring in polylogarithmic time
- On the complexity of distributed graph coloring
- Locality based graph coloring
- Local Distributed Decision
- What cannot be computed locally!
- Automata, Languages and Programming
- Distributed deterministic edge coloring using bounded neighborhood independence
This page was built for publication: Toward more localized local algorithms: removing assumptions concerning global knowledge
