Graphic matroids and the multicommodity transportation problem |
| |
Authors: | James R. Evans John J. Jarvis Richard A. Duke |
| |
Affiliation: | (1) University of Cincinnati, Cincinnati, OH, USA;(2) Georgia Institute of Technology, Atlanta, GA, USA |
| |
Abstract: | A necessary and sufficient condition for unimodularity in the multicommodity transportation problem is established, and the constructive proof yields an equivalent, single commodity network flow problem for the class of problems satisfying the condition. The concept of a graphic matroid is used to establish the transformation. |
| |
Keywords: | Multicommodity network flows Matroids Unimodularity |
本文献已被 SpringerLink 等数据库收录! |
|