Circulation problem: Difference between revisions

Revision as of 08:55, 12 March 2007

Revision as of 07:54, 1 November 2007

Line 44:

== Solution ==

For the circulation problem, many polynomial algorithms gavehave been developed (eg, 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 Complexity of Timetable and Multicommodity Flow Problems | publisher = SIAM | year = 1976 | journal = SIAM Journal on Computing | volume = 5 | number = 4 | pages = 691-703 | url = http://link.aip.org/link/?SMJ/5/691/1 | doi = 10.1137/0205048}}</ref>. For fractional flows, it is solvable in [[polynomial time]], as you can formulate the problem as a [[linear programming|linear program]].