Distributed computing with advice: information sensitivity of graph coloring
From MaRDI portal
Publication:2377267
DOI10.1007/s00446-008-0076-yzbMath1267.05118OpenAlexW1975011672MaRDI QIDQ2377267
Cyril Gavoille, David Ilcinkas, Pierre Fraigniaud, Andrzej Pelc
Publication date: 28 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-008-0076-y
Related Items
Byzantine gathering in polynomial time ⋮ The ANTS problem ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast rendezvous with advice ⋮ Unnamed Item ⋮ Drawing maps with advice ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Impact of knowledge on election time in anonymous networks ⋮ Communication algorithms with advice ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Trading Bit, Message, and Time Complexity of Distributed Algorithms ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Introduction to local certification ⋮ Topology recognition with advice
Cites Work
- Local MST computation with short advice
- Zero knowledge and the chromatic number
- Coloring unstructured radio networks
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring
- Locality in Distributed Graph Algorithms
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- On the Complexity of Distributed Network Decomposition
- On the complexity of distributed graph coloring
- Oracle size
- What can be computed locally?
- Graph Searching with Advice
- Distributed Computing – IWDC 2005
- What cannot be computed locally!
- Automata, Languages and Programming
- Tree Exploration with an Oracle
