Content deleted Content added
Timetable is one word, see also the original title of the manuscript. |
m Open access bot: url-access updated in citation with #oabot. |
||
| (One intermediate revision by one other user 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 timetable 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 ==
| |||