Smoothed Analysis of the Successive Shortest Path Algorithm

DOI10.1137/140989893zbMath1326.05039arXiv1501.05493MaRDI QIDQ3457194

Bodo Manthey, Heiko Röglin, Tobias Brunsch, Kamiel Cornelissen, Clemens Rösner

Publication date: 11 December 2015

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.05493

zbMATH Keywords

smoothed analysis; successive shortest path algorithm; minimum-cost flows

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C35: Extremal problems in graph theory

90C27: Combinatorial optimization

05C38: Paths and cycles

05C12: Distance in graphs

05C85: Graph algorithms (graph-theoretic aspects)