On the complexity of neighbourhood learning in radio networks

DOI10.1016/J.TCS.2015.04.027zbMATH Open1333.68078OpenAlexW2029877651MaRDI QIDQ896133FDOQ896133

Authors 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

lower boundsdeterministic algorithmsradio 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)

Recommendations

• On the complexity of fixed-schedule neighbourhood learning in wireless ad hoc radio networks
• Deterministic communication in radio networks
• scientific article; zbMATH DE number 1670865
• Radio Network Lower Bounds Made Easy
• Faster deterministic communication in radio networks

Cites Work

• scientific article; zbMATH DE number 4135867 (Why is no real title available?)
• scientific article; zbMATH DE number 1256716 (Why is no real title available?)
• scientific article; zbMATH DE number 1508646 (Why is no real title available?)
• scientific article; zbMATH DE number 3801449 (Why is no real title available?)
• An asymptotically fast nonadaptive algorithm for conflict resolution in multiple-access channels
• Broadcasting in UDG radio networks with unknown topology
• Deterministic communication in radio networks with large labels
• Distributed Computing: A Locality-Sensitive Approach
• Distributed backbone structure for algorithms in the SINR model of wireless networks
• Explicit Nonadaptive Combinatorial Group Testing Schemes
• Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others
• Families of finite sets in which no set is covered by the union of \(r\) others
• Generalized cover-free families.
• Nonrandom binary superimposed codes
• On \(r\)-cover-free families
• On local broadcasting schedules and CONGEST algorithms in the SINR model
• On the upper bound of the size of the \(r\)-cover-free families
• Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes
• Optimal Two-Stage Algorithms for Group Testing Problems
• Round complexity of leader election and gossiping in bidirectional radio networks
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)
• The capacity of wireless networks
• Time-efficient distributed layer-2 auto-configuration for cognitive radio networks

Cited In (4)

• New selectors and locally thin families with applications to multi-access channels supporting simultaneous transmissions
• On the complexity of fixed-schedule neighbourhood learning in wireless ad hoc radio networks
• Low-weight superimposed codes and related combinatorial structures: bounds and applications
• Bounds and algorithms for generalized superimposed codes

This page was built for publication: On the complexity of neighbourhood learning in radio networks

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