Toward more localized local algorithms: removing assumptions concerning global knowledge
From MaRDI portal
Publication:2441787
DOI10.1007/s00446-012-0174-8zbMath1284.68644arXiv1512.03306MaRDI 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
05C15: Coloring of graphs and hypergraphs
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
68W15: Distributed algorithms
Related Items
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?, Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics, Distributed Symmetry Breaking on Power Graphs via Sparsification, Improved deterministic distributed matching via rounding, Fast rendezvous on a cycle by agents with different speeds, The ANTS problem, Distributed algorithm for the maximal 2-packing in geometric outerplanar graphs
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
