TY - GEN

T1 - Finding disjoint paths in expanders deterministically and online

AU - Alon, Noga

AU - Capalbo, Michael

N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.

PY - 2007

Y1 - 2007

N2 - 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 expander G on n vertices, and a sequence of pairs si, ti, (1 ≤ i ≤ r) of vertices, where r = Θ(nd log d/log n), and no vertex appears more than d/3 times in the list of all endpoints s1, t 1,...,sr,tr. The algorithm outputs edge-disjoint paths Q1,...,Qr, where Qi connects si and ti. The paths are constructed online, that is, the algorithm produces Qi as soon as it gets si, ti 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 blow-ups of strong expanders.

AB - 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 expander G on n vertices, and a sequence of pairs si, ti, (1 ≤ i ≤ r) of vertices, where r = Θ(nd log d/log n), and no vertex appears more than d/3 times in the list of all endpoints s1, t 1,...,sr,tr. The algorithm outputs edge-disjoint paths Q1,...,Qr, where Qi connects si and ti. The paths are constructed online, that is, the algorithm produces Qi as soon as it gets si, ti 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 blow-ups of strong expanders.

UR - http://www.scopus.com/inward/record.url?scp=46749103286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46749103286&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2007.4389521

DO - 10.1109/FOCS.2007.4389521

M3 - Conference contribution

AN - SCOPUS:46749103286

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 518

EP - 524

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -