Minimal cost flows in regular matroids
Minimal cost flows in regular matroids
复制标题
常规拟阵中的最小成本流
DOI：
10.1007/bfb0120919
复制
发表时间：
1981
影响因子：
2.7
通讯作者：
H. Hamacher
中科院分区：
文献类型：
--
作者：
R. Burkard;H. Hamacher
本文考虑正则拟阵M中的流动，给出了用最小代价确定最大拟阵流的三种算法。第一种算法从任意最大的矩阵流开始，并通过在m中找到负电路来降低其成本。第二种算法通过从零流开始并沿着最短的增强电路进行增强来建立最小成本的矩阵流。最后一种算法适用于具有特殊结构的正则拟阵。通过一系列可允许的变换，可以找到最优的矩阵流。这种变换方法可以看作是求解线性分配问题的匈牙利方法的推广。本文所用的论证是纯组合型的，没有利用正则矩阵M用完全非模矩阵表示。
In this paper flows in regular matroids M are considered and three algorithms are described for determining maximal matroid flows with minimal costs. The first algorithms starts with an arbitrary maximal matroid flow and reduces its costs by finding negative circuits in M. The second builds up a min cost matroid flow by starting with the zero flow and performing augmentations along shortest augmenting circuits. The last algorithm works in regular matroids with special structures. By a sequence of admissible transformations an optimal matroid flow can be found. This transformation method can be viewed as a generalization of the Hungarian Method for solving linear assignment problems. The arguments used in the paper are of pure combinatorial kind and don’t make any use of the representation of the regular matroid M by a totally unimodular matrix.