Beeping a maximal independent set

DOI10.1007/s00446-012-0175-7zbMath1311.68024arXiv1206.0150OpenAlexW2568091325WikidataQ57203501 ScholiaQ57203501MaRDI QIDQ2441534

Ziv Bar-Joseph, Bernhard Haeupler, Noga Alon, Yehuda Afek, Fabian Kuhn, Alejandro Cornejo

Publication date: 25 March 2014

Published in: Lecture Notes in Computer Science, Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1206.0150

zbMATH Keywords

maximal independent setradio networksasynchronous wakeupbeeps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distributed systems (68M14)

Related Items (25)

Design patterns in beeping algorithms: examples, emulation, and analysis ⋮ The ANTS problem ⋮ Constant space and non-constant time in distributed computing ⋮ Counting in one-hop beeping networks ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ Computing large independent sets in a single round ⋮ Optimal Message-Passing with Noisy Beeps ⋮ Distributed Self-Stabilizing MIS with Few States and Weak Communication ⋮ Simple Neural-Like P Systems for Maximal Independent Set Selection ⋮ Patterns from nature: distributed greedy colouring with simple messages and minimal graph knowledge ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Transmitting once to elect a leader on wireless networks ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Global synchronization and consensus using beeps in a fault-prone multiple access channel ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Fast size approximation of a radio network in beeping model ⋮ Dynamic networks of finite state machines ⋮ The Synergy of Finite State Machines ⋮ Oblivious Collaboration ⋮ Noisy rumor spreading and plurality consensus ⋮ Asynchronous Broadcasting with Bivalent Beeps ⋮ Approximating the Size of a Radio Network in Beeping Model ⋮ Noisy beeping networks

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal bit complexity randomized distributed MIS algorithm
• Fast radio broadcasting with advice
• A log-star distributed maximal independent set algorithm for growth-bounded graphs
• A Biological Solution to a Fundamental Distributed Computing Problem
• An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract)
• The price of being near-sighted
• What Is the Use of Collision Detection (in Wireless Networks)?
• Deploying Wireless Networks with Beeps
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• Distributed Computing: A Locality-Sensitive Approach
• Maximal independent sets in radio networks
• Distributed Computing
• What cannot be computed locally!
• Self-organizing Desynchronization and TDMA on Wireless Sensor Networks

This page was built for publication: Beeping a maximal independent set