Transfinite Ford-Fulkerson on a finite network

DOI10.3233/COM-180082MaRDI QIDQ4628352zbMATH OpenOpenAlexFDO

Authors Spencer Backman, Tony Huynh

Publication date 20 March 2019

Published in Computability (Search for Journal in Brave)

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

zbMATH Keywords

network flowsordinals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10)

Abstract: It is well-known that the Ford-Fulkerson algorithm for finding a maximum flow in a network need not terminate if we allow the arc capacities to take irrational values. Every non-terminating example converges to a limit flow, but this limit flow need not be a maximum flow. Hence, one may pass to the limit and begin the algorithm again. In this way, we may view the Ford-Fulkerson algorithm as a transfinite algorithm. We analyze the transfinite running-time of the Ford-Fulkerson algorithm using ordinal numbers, and prove that the worst case running-time is $omeg{a}^{Theta(|E|)}$. For the lower bound, we show that we can model the Euclidean algorithm via Ford-Fulkerson on an auxiliary network. By running this example on a pair of incommensurable numbers, we obtain a new robust non-terminating example. We then describe how to glue $k$ copies of our Euclidean example in parallel to obtain running-time $omeg{a}^k$. An upper bound of $omeg{a}^{|E|}$ is established via induction on $|E|$. We conclude by illustrating a close connection to transfinite chip-firing as previously investigated by the first author.

Recommendations

• The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate
• Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
• On the efficiency of maximum-flow algorithms on networks with small integer capacities
• Improved Time Bounds for the Maximum Flow Problem
• An $o(n^3 )$-Time Maximum-Flow Algorithm

Cited in

(2)

• Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
• Removing null branches in a transfinite network

This page was built for publication: Transfinite Ford-Fulkerson on a finite network

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4628352)