The complexity of broadcasting in bounded-degree networks

1994/11/18 by Dinneen, Michael J.
#68q25 05c85 94c15 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.math/9411222

Abstract

Broadcasting concerns the dissemination of a message originating at one node of a network to all other nodes. This task is accomplished by placing a series of calls over the communication lines of the network between neighboring nodes, where each call requires a unit of time and a call can involve only two nodes. We show that for bounded-degree networks determining the minimum broadcast time from an originating node remains NP-complete.

Related

• Strong bounds and exact solutions to the minimum broadcast time problem
• Broadcast Graph Is NP-complete
• Broadcasting in Networks of Unknown Topology in the Presence of Swamping
• A Bound on the Throughput of Radio Networks
• Distributed Broadcast in Wireless Networks with Unknown Topology