EUVIMEDEUVIMED entdecken
Crossref

Edge-Disjoint Paths in Expanders: Online with Removals

Nemanja Draganić, Rajko Nenadov

SIAM Journal on Computing · 30.04.2026 · 55 (2) · 362-375

DOI: 10.1137/25m1724717 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 09.03.2026. Verfasst von Nemanja Draganić und 1 weiteren Autor:innen. Die Arbeit nennt 28 Literaturangaben. Gefördert von: SNSF.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong [Formula: see text]-regular expander graph [Formula: see text] with [Formula: see text] vertices. In particular, we describe a deterministic, polynomial time algorithm which maintains an initially empty collection of edge-disjoint paths [Formula: see text] in [Formula: see text] and fulfills any series of two types of requests: (1) Given two vertices [Formula: see text] and [Formula: see text] such that each appears as an endpoint in [Formula: see text] paths in [Formula: see text] and, additionally, [Formula: see text], the algorithm finds a path of length at most [Formula: see text] connecting [Formula: see text] and [Formula: see text] which is edge-disjoint from all other paths in [Formula: see text], and adds it to [Formula: see text]. (2) Remove a given path [Formula: see text] from [Formula: see text]. Importantly, each request is processed before seeing the next one. The upper bound on the length of found paths and the constraints are the best possible up to a constant factor. This establishes the first online algorithm for finding edge-disjoint paths in expanders which also allows removals, significantly strengthening a long list of previous results on the topic. We obtain the same result in the case [Formula: see text] is directed.

Förderung

  • SNSF

Zitieren

APA

Draganić, N., & Nenadov, R. (2026). Edge-Disjoint Paths in Expanders: Online with Removals. SIAM Journal on Computing, 55(2), 362-375. https://doi.org/10.1137/25m1724717

Vancouver

Draganić N, Nenadov R. Edge-Disjoint Paths in Expanders: Online with Removals. SIAM Journal on Computing. 2026;55(2):362-375. doi:10.1137/25m1724717

BibTeX
@article{Dragani2026,
  author = {Draganić, Nemanja and Nenadov, Rajko},
  title = {Edge-Disjoint Paths in Expanders: Online with Removals},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {2},
  pages = {362--375},
  doi = {10.1137/25m1724717}
}
Kostenlos starten →