BROWSE
Detail
Conference Paper
On Algorithms for Minimum-Cost Quickest Paths with Multiple Delay-Bounds
Cited - time in 
Share 
Share
- Authors
- Hak Suh Kim, Byung Jun Ahn, Soo Hyun Park, In Ki Hong, Young Cheol Bang
- Issue Date
- 2004-02
- Citation
- International Conference on Advanced Communication Technology (ICACT) 2004, pp.941-944
- Publisher
- IEEE
- Language
- English
- Type
- Conference Paper
- Abstract
- The quickest path problem deals with the transmission of a message of size σ from a source to a destination with the minimum end-to-end delay over a network with bandwidth and delay constraints on the links. We adapt properties of the quickest path to solve the delay-bounded minimum-cost (DBMC) path problem that is known to be the NP-hard. In this paper, we propose two efficient and simple algorithms, DBMCQP and DBMCQRT. DBMCQP computes a DBMC quickest path for a given message size σ with O(rm + rnlogn), and DBMCQRT construct DBMC routing tables taking into account multiple delay-bounds for any size of message with O(kr2), where r, n, m, and k are the number of distinct link-bandwidths, nodes, links of the network, and the number of delay-bounds, respectively.