On the complexity of neighbourhood learning in radio networks

DOI10.1016/j.tcs.2015.04.027zbMath1333.68078OpenAlexW2029877651MaRDI QIDQ896133

Avery Miller

Publication date: 11 December 2015

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

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

zbMATH Keywords

deterministic algorithmslower boundsradio networksneighbourhood learning taskset families

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Bounds and algorithms for generalized superimposed codes ⋮ Low-weight superimposed codes and related combinatorial structures: bounds and applications ⋮ New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions

Cites Work

• Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others
• Deterministic communication in radio networks with large labels
• Families of finite sets in which no set is covered by the union of \(r\) others
• On the upper bound of the size of the \(r\)-cover-free families
• Generalized cover-free families.
• On local broadcasting schedules and CONGEST algorithms in the SINR model
• On \(r\)-cover-free families
• Broadcasting in UDG radio networks with unknown topology
• Round complexity of leader election and gossiping in bidirectional radio networks
• Time-efficient distributed layer-2 auto-configuration for cognitive radio networks
• Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
• The capacity of wireless networks
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Backbone Structure for Algorithms in the SINR Model of Wireless Networks
• An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
• Explicit Nonadaptive Combinatorial Group Testing Schemes
• Optimal Two-Stage Algorithms for Group Testing Problems
• Nonrandom binary superimposed codes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item