Finding disjoint paths in expanders deterministically and online

Noga Alon, Michael Capalbo

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages518-524
Number of pages7
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Finding disjoint paths in expanders deterministically and online'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., & Capalbo, M. (2007). Finding disjoint paths in expanders deterministically and online. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 (pp. 518-524). [4389521] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389521