Paper Info
Title
Efficient Delay Routing (Extended Abstract)
Abstract
In this paper the computational complexity of finding minimum end-to-end delay packet routing schemes is studied. The existence of polynomial-time algorithms able to optimize both the end-to-end delay achievable when the number of packets in the network increases, and the number of packets that can be accepted in the network in order to keep the end-to-end delay within a constant value is investigated. In particular, it is proved the hardness of approximating in polynomial time both the minimum end-to-end delay and the maximum number of accepted packets even within a sublinear error in the number of packets.
Year
DOI
Venue
1996
10.1007/3-540-61626-8_34
Euro-Par, Vol. I
Keywords
Field
DocType
extended abstract,efficient delay routing,computational complexity,polynomial time,hardness of approximation,end to end delay
Equal-cost multi-path routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,Elmore delay
Conference
ISBN
Citations 
PageRank 
3-540-61626-8
0
0.34
References 
Authors
1
1
Name
Order
Citations
PageRank
Miriam di Ianni114417.27