loading...
Finding Disjoint Paths in Expanders Deterministically and Online
Providence, Rhode Island October 21-October 23
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.1948th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We describe a deterministic, polynomial time algorithm for finding edge-disjoint paths connecting given pairs of vertices in an expander. Specifically, the input of the algorithm is a sufficiently strong d-regular expanderG on n vertices, and a sequence of pairs s_i ,t_i ,(1 \leqslant i \leqslant r) of vertices, where r = \Theta (\frac{{nd\log d}} {{\log n}}), and no vertex appears more than d/3 times in the list of all endpoints s_1 ,t_1 , \ldots ,s_r ,t_r. The algorithm outputs edge-disjoint paths Q_1 , \ldots ,Q_r , where Q_1 connects s_i and t_i. The paths are constructed online, that is, the algorithm produces Q_i as soon as it gets s_i ,t_i and before the next requests in the sequence are revealed. This improves in several respects a long list of previous algorithms for the above problem, whose study is motivated by the investigation of communication networks. An analogous result is established for vertex disjoint paths in blowups of strong expanders.
Citation:
Noga Alon, Michael Capalbo, "Finding Disjoint Paths in Expanders Deterministically and Online," focs, pp.518-524, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.