ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
ALGORITHMS FOR SOLVING THE INDEPENDENT-FLOW PROBLEMS
复制标题
解决独立流问题的算法
DOI：
10.15807/jorsj.21.189
复制
发表时间：
1978
影响因子：
--
通讯作者：
S. Fujishige
中科院分区：
文献类型：
--
作者：
S. Fujishige
给定一个具有定义了多拟阵的入口顶点集VI和出口顶点集V2的有能力网络，独立流是网络中的流，使得对应于VI中的供给的向量和对应于V2中的需求的向量分别是VI和V2上的多阵的独立向量。 本文考虑的独立流问题有以下两个： (1)找到最大独立流； (2)寻找最优独立流，即当给每个弧赋予成本时，最小成本的最大独立流。我们提出了几个在算法上描述最佳独立流的定理，并基于这些定理提出了解决独立流问题的算法。
Given a capacitated network with the entrance· vertex set VI and the exit-vertex set V2 on which polymatroids are defmed, an independent flow is a flow in the network such that a vector corresponding to the supplies in VI and a vector corresponding to the demands in V2 are, respectively, independent vectors of the polymatroids on VI and V2 • The independent-flow problems considered in the present paper are the following two: (1) to find a maximum independent flow; and (2) to find an optimal independent flow, i.e., a maximum independent flow of the minimum cost when a cost is given to each arc. We present several theorems which algorithmically characterize optimal independent flows and we propose algorithms for solving the independent-flow problems based on the theorems.