The complexity of broadcasting in bounded-degree networks

arXivmath/9411222MaRDI QIDQ6503565FDOQ6503565

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.

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Applications of graph theory to circuits and networks (94C15)

This page was built for publication: The complexity of broadcasting in bounded-degree networks

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