Transmissions in a network with capacities and delays

Transmissions in a network with capacities and delays

0.00 Avg rating0 Votes
Article ID: iaor20022322
Country: United States
Volume: 33
Issue: 3
Start Page Number: 167
End Page Number: 174
Publication Date: May 1999
Journal: Networks
Authors: , , ,
Keywords: networks: path
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 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.

Reviews

Required fields are marked *. Your email address will not be published.