Transmissions in a network with capacities and delays

Citation
D. Kagaris et al., Transmissions in a network with capacities and delays, NETWORKS, 33(3), 1999, pp. 167-174
Citations number
11
Categorie Soggetti
Computer Science & Engineering
Journal title
NETWORKS
ISSN journal
00283045 → ACNP
Volume
33
Issue
3
Year of publication
1999
Pages
167 - 174
Database
ISI
SICI code
0028-3045(199905)33:3<167:TIANWC>2.0.ZU;2-X
Abstract
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.