research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleTransmissions in a Network with Capacities and Delays
Bibtex cite IDRACTI-RU1-1999-14
Journal Networks
Year published 1999
Volume 33
Number 3
Pages 167-174
Keywords data transmission; sparse network; transmission time; quickest path; dynamic algorithm
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 quickest path, and present algorithms for general and special classes of networks that improve upon previous approaches. The first dynamic algorithm for the quickest path problem is also given
Kagaris, D.
Pantziou, Grammati
Tragoudas, S.
Zaroliagis, Christos
J12-networks-99.pdf (main file)
Publication ID415