Broadcasting and NP-completeness
Jean‐Claude Bermond, Pierre Fraigniaud · 1991
In this note, we answer two questions arising in broadcasting problems in networks. We first describe a new family of minimum broadcast graphs. Then we give a proof due to Alon of the NP-completeness of finding disjoint spanning trees of minimum depth, rooted at a given vertex. 1 Introduction In the design and use of parallel computers, different elements are important. Among them are the topology of the interconnection network and the communication scheme. In this paper, we focus on one important communication problem: Broadcasting = Sending a message from a given vertex to all other vertices. The initiator is also called the root, and the broadcasting problem is also called OTA (OneTo -All). We consider the usual store-and-forward model for routing, in which a message that passes through intermediate nodes is stored in each intermediate processor before reaching its final destination. Two kinds of communication schemes are usually considered: half duplex and full duplex. In t...