Michael J. Dinneen
Published 1994-11-18Version 1
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.
Conflict-free connections: algorithm and complexity
The complexity of the $q$-analog of the $n$-cube
On the complexity of computing the $k$-metric dimension of graphs
![QR code for arXiv:math/9411222 [math.CO]](http://oss.arxitics.com/images/favicon.svg)