Premium
The fractional congestion bound for efficient edge disjoint routing
Author(s) -
Baveja Alok
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20216
Subject(s) - disjoint sets , routing (electronic design automation) , mathematics , enhanced data rates for gsm evolution , upper and lower bounds , path (computing) , combinatorics , relaxation (psychology) , computer science , discrete mathematics , computer network , telecommunications , psychology , mathematical analysis , social psychology
This article investigates the following problem: Given the fractional relaxation of the edge disjoint routing problem, how small a fractional congestion is sufficient to guarantee efficient edge disjoint routing? That is, what is the largest possible value v such that a fractional flow with congestion at most v , can be efficiently converted into an edge disjoint routing? Leighton, Lu, Rao, and Srinivasan (SIAM J Comput 2001) have established that fractional congestion of at most the order of O (1/( d log k )) is sufficient, where d is the maximum path length in the fractional relaxation, and k is the number of pairs to be routed. It is also known that Θ (1/ d ) is the correct bound, if we are only interested in an existence result (Leighton, Rao, and Srinivasan, Hawaii International Conference on System Sciences, 1998). Motivated by the fact that d is small for many types of routing problems, specifically, polylogarithmic for expander graphs, this article improves upon the former result by showing O (1/( d log d )) fractional congestion to suffice. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008