On the complexity of timetable and multi-commodity flow problems¶
Even, S., Itai, A., & Shamir, A. (1976). On the complexity of timetable and multi-commodity flow problems. SIAM Journal on Computing, 5(4), 691-703.
Cited by¶
2 citations across 2 artifacts.
Each citation links to the sentence it supports in the citing article.
Domain-specific¶
Mechanisms¶
- Multi-Commodity Flow Model
- Integer multi-commodity flow — insisting each commodity follow whole paths — is NP-hard, so realistic instances can become intractable as commodities multiply.
This sourceProves that integral multicommodity flow is NP-complete even for two commodities, establishing its potential computational intractability.
- Integer multi-commodity flow — insisting each commodity follow whole paths — is NP-hard, so realistic instances can become intractable as commodities multiply.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Not recorded. Neither this nor any other of the 2 citations of this work carries a recorded support check.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Registry ID ref:fa7ed0ce1916 · see in the full table