KIT | KIT-Bibliothek | Impressum | Datenschutz

Efficiently computing maximum flows in scale-free networks

Bläsius, Thomas ORCID iD icon; Friedrich, Tobias; Weyand, Christopher


We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz’s algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz’s original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph.
Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.

Verlagsausgabe §
DOI: 10.5445/IR/1000138389
Veröffentlicht am 01.10.2021
DOI: 10.4230/LIPIcs.ESA.2021.21
Zitationen: 1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-9597720-4-4
ISSN: 1868-8969
KITopen-ID: 1000138389
HGF-Programm 46.21.02 (POF IV, LK 01) Cross-Domain ATMLs and Research Groups
Erschienen in 29th Annual European Symposium on Algorithms (ESA 2021): 6-8 September 2021, online. Ed.: P. Mutzel
Veranstaltung 29th Annual European Symposium on Algorithms (ESA 2021), Online, 06.09.2021 – 08.09.2021
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten Art.-Nr.: 21
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 204
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page