Maximal independent sets in radio networks

DOI10.1145/1073814.1073842zbMath1314.68163OpenAlexW2147408677MaRDI QIDQ5177236

Roger Wattenhofer, Thomas Moscibroda

Publication date: 10 March 2015

Published in: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1073814.1073842

zbMATH Keywords

clustering ad hoc networks radio network sensor networks initialization \textsc{Maximal Independent Sets}asynchronous wake-up

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Stochastic network models in operations research (90B15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (42)

Nearly optimal bounds for distributed wireless scheduling in the SINR model ⋮ Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ Distributed construction of low-interference spanners ⋮ Broadcasting in UDG radio networks with missing and inaccurate information ⋮ Contention-free MAC protocols for asynchronous wireless sensor networks ⋮ Consensus and collision detectors in radio networks ⋮ Coloring unstructured radio networks ⋮ Broadcasting in UDG radio networks with unknown topology ⋮ Randomised distributed MIS and colouring algorithms for rings with oriented edges in \(O(\sqrt{\log n})\) bit rounds ⋮ Constant-approximation for optimal data aggregation with physical interference ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Network design under general wireless interference ⋮ Distributed approximation of capacitated dominating sets ⋮ Optimal bit complexity randomised distributed MIS and maximal matching algorithms for anonymous rings ⋮ The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication ⋮ Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks ⋮ The distributed wireless gathering problem ⋮ The Distributed Wireless Gathering Problem ⋮ Computing large independent sets in a single round ⋮ Uniting General-Graph and Geometric-Based Radio Networks via Independence Number Parametrization ⋮ Beeping a maximal independent set ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Broadcasting in UDG Radio Networks with Missing and Inaccurate Information ⋮ Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges ⋮ Sensor Network Gossiping or How to Break the Broadcast Lower Bound ⋮ The abstract MAC layer ⋮ Independent sets in graphs ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Þ-energy of generalized Petersen graphs ⋮ Contention resolution on a fading channel ⋮ A note on uniform power connectivity in the physical signal to interference plus noise (SINR) model ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ The cost of global broadcast in dynamic radio networks ⋮ Empire of colonies: Self-stabilizing and self-organizing distributed algorithm ⋮ Minimum Total Node Interference in Wireless Sensor Networks ⋮ Distributed \((\varDelta + 1)\)-coloring in the physical model ⋮ On the effect of the deployment setting on broadcasting in Euclidean radio networks ⋮ Equilibria of Games in Networks for Local Tasks ⋮ Fault-Tolerant Consensus with an Abstract MAC Layer. ⋮ An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) ⋮ Unnamed Item ⋮ Analysis of fully distributed splitting and naming probabilistic procedures and applications

This page was built for publication: Maximal independent sets in radio networks