arXiv Open Access 2022

Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time

Gramoz Goranci Monika Henzinger

Lihat Sumber

Abstrak

We show an $(1+ε)$-approximation algorithm for maintaining maximum $s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)} ε^{-1/2}$ amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee.

Topik & Kata Kunci

cs.DS

Penulis (2)

Gramoz Goranci

Monika Henzinger

Format Sitasi

APA MLA BibTeX

Goranci, G., Henzinger, M. (2022). Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time. https://arxiv.org/abs/2211.09606

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2022
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓