Multi-commodity flow

From Glossary

Jump to: navigation, search

A network flow problem in which more than one commodity share arc capacities. This applies to communication networks as well as to shipments of different grains on barges of limited capacities. It is more complicated than the single-commodity flow, generally NP-complete (except for some special cases). See [1] for one of the complexities.

Personal tools