Transmissions in a network with capacities and delays

We examine the problem of transmitting in minimum time a given amount of da ta between a source and a destination in a network with finite channel capa cities and nonzero propagation delays. In the absence of delays, the proble m has been shown to be solvable in polynomial time. In this paper, we show that the general problem is NP-complete. In addition, we examine transmissi ons along a single path, called the quickest path, and present algorithms f or general and special classes of networks that improve upon previous appro aches. The first dynamic algorithm for the quickest path problem is also gi ven. (C) 1999 John Wiley & Sons, Inc.