Multicommodity Flow in Polynomial Time
classification
🧮 math.CO
cs.DMcs.DSmath.OC
keywords
flowmulticommoditypolynomialproblemtimeablealreadybipartite
read the original abstract
The multicommodity flow problem is NP-hard already for two commodities over bipartite graphs. Nonetheless, using our recent theory of n-fold integer programming and extensions developed herein, we are able to establish the surprising polynomial time solvability of the problem in two broad situations.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.