From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Abstract
We provide faster strongly polynomial time algorithms solving maximum flow in structured \(n\)-node \(m\)-arc networks. Our results imply an \(n^{\omega+o(1)}\)-time strongly polynomial time algorithms for computing a maximum bipartite \(b\)-matching where \(\omega\) is the matrix multiplication constant. Additionally, they imply an \(m^{1+o(1)}W\)-time algorithm for solving the problem on graphs with a given tree decomposition of width \(W\).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Complex Network Analysis Techniques
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 150–163
- Publication date
- 1 January 2026
- Language
- EN