Distributed \((\varDelta + 1)\)-coloring in the physical model

DOI10.1016/j.tcs.2014.05.016zbMath1417.68279OpenAlexW2181222287MaRDI QIDQ742411

Dongxiao Yu, Yuexuan Wang, Qiang-Sheng Hua, Francis C. M. Lau

Publication date: 18 September 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.05.016

zbMATH Keywords

randomized algorithmcoloringdistributed algorithmphysical interference modelwireless ad-hoc and sensor networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (2)

Simple Distributed Δ + 1 Coloring in the SINR Model ⋮ Fully dynamic MIS in uniformly sparse graphs

Cites Work

• Nearly optimal bounds for distributed wireless scheduling in the SINR model
• Coloring unstructured radio networks
• Distributed Deterministic Broadcasting in Uniform-Power Ad Hoc Wireless Networks
• Distributed Multiple-Message Broadcast in Wireless Ad-Hoc Networks under the SINR Model
• Broadcast in the Ad Hoc SINR Model
• Distributed Contention Resolution in Wireless Networks
• Deterministic coin tossing with applications to optimal parallel list ranking
• The capacity of wireless networks
• Coloring unstructured wireless multi-hop networks
• Distributed (δ+1)-coloring in linear (in δ) time
• Maximal independent sets in radio networks
• Distributed Deterministic Broadcasting in Wireless Networks of Weak Devices
• The Power of Non-Uniform Wireless Power

This page was built for publication: Distributed \((\varDelta + 1)\)-coloring in the physical model