2017/05/03 by Mark de Berg, de Berg, Mark, Hans L. Bodlaender +3
Computer Science · Engineering · #Antenna Design and Analysis #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #F.1.3 #F.2.2 #FOS: Computer and information sciences #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1705.01465
openalex publication_date 2017/05/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Let P be a set of nodes in a wireless network, where each node is modeled as a point in the plane, and let s∈ P be a given source node. Each node p can transmit information to all other nodes within unit distance, provided p is activated. The (homogeneous) broadcast problem is to activate a minimum number of nodes such that in the resulting directed communication graph, the source s can reach any other node. We study the complexity of the regular and the hop-bounded version of the problem (in the latter, s must be able to reach every node within a specified number of hops), with the restriction that all points lie inside a strip of width w. We almost completely characterize the complexity of both the regular and the hop-bounded versions as a function of the strip width w.