Circulation problem: Difference between revisions

Revision as of 01:11, 4 April 2023

Latest revision as of 16:42, 24 May 2025

(2 intermediate revisions by 2 users not shown)

Line 40:

== Solution ==

For the circulation problem, many polynomial algorithms have been developed (e.g., [[Edmonds–Karp algorithm]], 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.<ref name="Ta85">{{cite journal | author = Éva Tardos | title = A strongly polynomial minimum cost circulation algorithm | journal = Combinatorica | date = 1985 | volume = 5 | issue = 3 | pages = 247–255 | doi = 10.1007/BF02579369}}</ref>

<!-- which articles? -->

For the case of multiple commodities, the problem is [[NP-complete]] for integer flows.<ref name="EIS76">{{cite journal | author = S. Even and A. Itai and A. Shamir | title = On the complexity of time tabletimetable and multi-commodity flow problems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | pages = 691–703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048 | issue = 4 | url-status = dead | archiveurl = https://archive.today/20130112133748/http://link.aip.org/link/?SMJ/5/691/1 | archivedate = 2013-01-12 | url-access = subscription }}</ref> For fractional flows, it is solvable in [[polynomial time]], as one can formulate the problem as a [[linear programming|linear program]].

== Related problems ==