Circulation problem: Difference between revisions

Revision as of 16:39, 24 February 2012

Revision as of 09:13, 5 July 2012

Line 35:

For the circulation problem, many polynomial algorithms have been developed (e.g., [[Edmonds-Karp algorithm|Edmonds and Karp]], 1972; Tarjan 1987-1988). <!-- 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 Complexitycomplexity of Timetabletime table and Multicommoditymulti-commodity Flowflow Problemsproblems | 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}}</ref> For fractional flows, it is solvable in [[polynomial time]], as one can formulate the problem as a [[linear programming|linear program]].

== Related problems ==