Coloring unstructured radio networks

DOI10.1007/s00446-008-0070-4zbMath1267.68042OpenAlexW1976011215MaRDI QIDQ2377260

Roger Wattenhofer, Thomas Moscibroda

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-0070-4

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (13)

Broadcasting in UDG radio networks with missing and inaccurate information ⋮ Contention-free MAC protocols for asynchronous wireless sensor networks ⋮ Coloring unstructured radio networks ⋮ Broadcasting in UDG radio networks with unknown topology ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Simple Distributed Δ + 1 Coloring in the SINR Model ⋮ Leveraging multiple channels in ad hoc networks ⋮ Broadcasting in UDG Radio Networks with Missing and Inaccurate Information ⋮ Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges ⋮ An optimal bit complexity randomized distributed MIS algorithm ⋮ A near optimal periodic transmission schedule in bounded degree wireless sensor network ⋮ Distributed \((\varDelta + 1)\)-coloring in the physical model ⋮ On the effect of the deployment setting on broadcasting in Euclidean radio networks

Cites Work

• Unnamed Item
• Parallel \((\Delta +1)\)-coloring of constant-degree graphs
• On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization
• Coloring unstructured radio networks
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• Locality in Distributed Graph Algorithms
• Packet Switching in Radio Channels: Part II--The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution
• Distributed Computing: A Locality-Sensitive Approach
• The wakeup problem in synchronous broadcast systems (extended abstract)
• On the locality of bounded growth
• Maximal independent sets in radio networks
• Contention-Free MAC Protocols for Wireless Sensor Networks
• Algorithms – ESA 2004
• Algorithms – ESA 2005
• Models and approximation algorithms for channel assignment in radio networks

This page was built for publication: Coloring unstructured radio networks