Abstract: We examine the problem of transmitting in minimum time a given amount of data between a
source and a destination in a network with finite channel capacities and nonzero propagation delays. In
the absence of delays, the problem 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 transmissions along a single path,
called the quickestpath, and present algorithms for general and special classes of networks that improve
upon previous approaches. The first dynamic algorithm for the quickestpath problem is also
given