Minimal path broadcast networks

Broadcasting is the communication process whereby a message that is initially known by one site becomes known to all sites of a network. Messages are transmitted by calls from senders to sets of receivers. In path broadcasting, a site can call nonneighboring sites over paths in the network. A call occupies all sites and edges on the path followed by the call; thus, any calls made concurrently must be vertex‐disjoint. We discuss the design of sparse networks that allow path broadcasting to be completed in minimum time under three different path broadcast models. © 2004 Wiley Periodicals, Inc.