Multicommodity Network Flows with Safety Considerations

Y. L. Chen and Y. H. Chin
Additional contact information
Y. L. Chen: National Central University, Chung-Li, Taiwan, ROC
Y. H. Chin: National Tsing Hua University, Hsinchu, Taiwan, ROC

Operations Research, 1992, vol. 40, issue 1-supplement-1, S48-S55

Abstract: Previous research on the multicommodity minimum cost flow problem (MMCFP) has assumed that there are two types of values associated with an arc. The first is the capacity of the arc and the second is the unit flow cost along the arc. This paper adds the third attribute—the degree of difficulty—into the conventional model of the MMCFP. In this way, a new problem, which is more general and difficult than the conventional MMCFP, is formed. However, we show that these two problems are indeed polynomially equivalent. With the equivalence, the techniques developed for solving the conventional MMCFP can be used to solve the new but more general problem.

Keywords: networks/graphs; flow algorithms: polynomial equivalence of multicommodity network flow problem (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.1.S48 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:40:y:1992:i:1-supplement-1:p:s48-s55

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().