Distributed computing with advice: information sensitivity of graph coloring

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

zbMATH Keywords

graph coloringdistributed computingadviceamount of informationnetwork algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Distributed systems (68M14)

Related Items (15)

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

This page was built for publication: Distributed computing with advice: information sensitivity of graph coloring