### 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 s_{i}, t^{i}, (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 s_{1}, t _{1},...,s_{r},t_{r}. The algorithm outputs edge-disjoint paths Q_{1},...,Q_{r}, where Q_{i} 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 blow-ups of strong expanders.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 |

Pages | 518-524 |

Number of pages | 7 |

DOIs | |

State | Published - Dec 1 2007 |

Externally published | Yes |

Event | 48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States Duration: Oct 20 2007 → Oct 23 2007 |

### Publication series

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

ISSN (Print) | 0272-5428 |

### Other

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

Country | United States |

City | Providence, RI |

Period | 10/20/07 → 10/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

*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