最小网络问题及其多项式时间算法

Minimum network problem and its time-based polynomial algorithm

针对债务清理问题和某些物流问题的实际应用背景,提出一类网络最优化模型——最小网络问题。讨论了最小网络的相关性质,获得了最小网络的若干充分必要条件。证明了任一网络可通过两种基本运算化为最小网络,由此得出了将任一网络化为最小网络的方法。给出了求给定网络的最小网络的一个多项式时间算法。

The minimum network problem is a network optimization problem related to the retiring of a chain of debts and to some material flow problems. This paper analyzes the properties of a minimum network, and necessary and sufficient conditions for a minimum network. The analysis proves that any network can be reduced to one of its minimum networks by two basic operations. A method was developed to reduce any network to its minimum network using a timebased polynomial algorithm.