Coloring unstructured radio networks

DOI10.1007/S00446-008-0070-4MaRDI QIDQ2377260zbMATH OpenOpenAlexFDO

Authors Thomas Moscibroda, Roger Wattenhofer

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

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

Recommendations

• Coloring unstructured wireless multi-hop networks
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Distributed \((\varDelta + 1)\)-coloring in the physical model
• Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
• Simple Distributed Δ + 1 Coloring in the SINR Model

Cites work

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

Cited in

(16)

• 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
• Broadcasting in UDG Radio Networks with Missing and Inaccurate Information
• Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges
• Deploying wireless networks with beeps
• Coloring unstructured wireless multi-hop networks
• Experimental evaluation of distributed node coloring algorithms for wireless networks
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• On the effect of the deployment setting on broadcasting in Euclidean radio networks
• 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

This page was built for publication: Coloring unstructured radio networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2377260)