带分解功能的网络最大流问题

本文在[1]和[5]的基础上,研究最大网络流问题.与已有的研究不同的是,本文对最大流问题进行了分解,即把最大流网络分解成几个相互独立的子网络.     

求解最大利润流问题的一个算法

为了便于建立与最大利润流问题有关的决策支持系统，本给出了一个交易网络中求最大利润流的数值算法，证明了算法的理论依据，并举例了说明算法的应用。该算法能求得问题的最优解，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

基于结构元理论的模糊最大流算法研究

运用结构元理论来求解模糊弧容量网络的最大流问题.先简要介绍模糊结构元及相关定理.之后证明了模糊网络最大流的判定定理,该定理表明:求模糊网络最大流等价求一经典网络最大流.最后,通过一个例子来说明求解过程。     

一类两种商品的网络流问题

本文考虑在有两个发点x1和x2，两个收点y1和y2的网络中，求把商品1从x1运送到y1，把商品2从x2运送到y2的最大流问题，给出一个充分必要条件，指出在一般情况下无最大流，但可以得到满意流，最后给出一个算例。     

有上下界网络最大流与最小截问题

为了便于建立与有上下界网络最大流与最小截问题有关的决策支持系统，本文给出一个求有上下界网络最大流与最小截的数值算法，证明了算法的理论依据，并举例说明了算法在堵塞流理论中的应用。该算法能判定问题是否有可行解，在问题有可行解的情况下能求得问题的最优解。该算法具有易于编程实现、收敛性好等优点。数值实验表明该算法有较高的计算效率，可用于求解最小饱和流问题。     

会计数据的网络流分析

学者已证明一个会计主体如一家企业、其复式簿记中一级账户记录的数据组成一个矩阵;继而提出了会计回路概念,并认识到会计回路符合网络的某些规律.提出复式簿记系统的矩阵对应于1个网络,该网络存在着网络流.图论中的最大流最小割定理在该网络中同样有效,可以对之求解最大流最小割.最小割的集合是网络中的"瓶颈",直接影响着总的通过流量.计算出最小割的值,找出它由哪些会计分录组成、关联到哪些会计科目、流量是多少,这正是该会计主体运营中的薄弱环节.这是会计史上第一种整体地、定量地分析会计主体运营状况的数学方法.     

网络最大流算法的性能分析

对网络最大流问题的求解算法进行性能分析和比较.结果表明,与经典的增载轨算法相比,基于动态规划思想的算法将最大流的求解过程看作一个动态调整过程,通过判断在各个动态阶段各节点允许通过的最大流量,从而能更快的得到网络的最大流值.同时文中的算法分析进一步为这一算法建立了严格的理论基础.     

考虑路损的最大流问题及其基本特征

本文给出了考虑流量损耗的最大流问题的数学模型,并阐明了该问题的几个基本特征.     

紧急网络中的最小饱和流问题

网络N中的一个流,如果沿前向已无法再增流,则称为饱和流,在交通拥挤或紧急疏散时,网络往往被一饱和流所堵塞。显然,这饱和流的值越小,网络的性能就越差。于是从网络分析的观点就提出最小饱和流问题。本文首先证明此问题NP－困难的。然后给出关于最小饱和流与最大流的关系及算法方面的结果。     

求解网络最大流问题的一个算法

为了便于建立与网络最大流问题有关的决策支持系统，本给出一个求解网络最大流问题的数值算法。证明了算法的理论依据，并举例说明了算法的应用。该算法能求出网络最大流和最小截，并具有易于编程实现、收敛性好等优点，大量数值实验表明该算法非常实用有效。     

Simplifying maximum flow computations: The effect of shrinking and good initial flows

Maximum flow problems occur in a wide range of applications. Although already well studied, they are still an area of active research. The fastest available implementations for determining maximum flows in graphs are either based on augmenting path or on push-relabel algorithms. In this work, we present two ingredients that, appropriately used, can considerably speed up these methods. On the theoretical side, we present flow-conserving conditions under which subgraphs can be contracted to a single vertex. These rules are in the same spirit as presented by Padberg and Rinaldi (1990) [12] for the minimum cut problem in graphs. These rules allow the reduction of known worst-case instances for different maximum flow algorithms to equivalent trivial instances. On the practical side, we propose a two-step max-flow algorithm for solving the problem on instances coming from physics and computer vision. In the two-step algorithm, flow is first sent along augmenting paths of restricted lengths only. Starting from this flow, the problem is then solved to optimality using some known max-flow methods. By extensive experiments on instances coming from applications in theoretical physics and computer vision, we show that a suitable combination of the proposed techniques speeds up traditionally used methods.     

An improved algorithm for decomposing arc flows into multipath flows

We consider a multipath maximum flow problem introduced by Kishimoto (Networks 27(4)(1996)279-291). The focus is on efficient transformation from arc flows into multipath flows, where a multipath flow is a nonnegative combination of multipaths. A new algorithm that is more efficient than existing ones is proposed for the transformation.     

Maximum skew-symmetric flows and matchings

The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte [28] in terms of self-conjugate flows in antisymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp [7] and the blocking flow method of Dinits [4], obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit node capacities our blocking skew-symmetric flow algorithm has time bounds similar to those established in [8, 21] for Dinits algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in time, which matches the time bound for the algorithm of Micali and Vazirani [25]. Finally, extending a clique compression technique of Feder and Motwani [9] to particular skew-symmetric graphs, we speed up the implied maximum matching algorithm to run in time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on skew-symmetric flows and their applications are presented.Mathematics Subject Classification (1991): 90C27, 90B10, 90C10, 05C85     

Berge’s theorem for the maximum charge problem

In 1957 Berge [C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957) 842–844] established that a matching is maximum if and only if there are no augmenting paths in the graph. In this paper we prove Berge’s result for a generalization of the matching problem—the maximum charge problem with capacity constraints. We show that a charge is maximum if and only if there is no alternating path, or lasso, along which the charge can be augmented.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

带有模糊容量限制的网络中的最佳最小费用最大流

本文主要讨论当网络中的弧容量限制和最大流目标要求带有模糊性时的最小费用最大流问题，通过构造带费用的增量网络并设法寻找其中的最佳最小费用路，给出了求解这类模糊网络流问题的算法。     

Maximum flow in a network with fuzzy arc capacities

Our main concern is the maximum flow in a network in which an excess over the beforehand fixed quota of arc capacity is admissible. The problem is represented as a partially fuzzy linear programming task. A theorem equivalent to the Ford and Fulkerson one concerning the classic task of maximum flow is proved in the paper. An algorithm for searching maximum flow assuming integer values of flows on network arcs is presented.     

The final answer to the complexity of a basic problem in resilient network design

To provide resilience to failures of the multi-commodity flow network, either in the failure-free state flows can be routed along multiple paths and over-dimensioned, or whenever a failure occurs flows can be restored along unaffected paths. The complexity of the network design depends on the selected method of providing resilience and on a number of design options—whether single or multiple commodities and single- or multi-element failures are considered, if the reaction to failures is dependent or independent on the failure, which mechanism of capacity release and reuse is applied, etc. For almost all combinations of those choices either the corresponding design problem has already been shown to be NP-hard or a compact linear programming formulation of the problem has been provided. The only case that has resisted an answer is when flows are restored in a state-dependent manner using the stub release mechanism. In this paper it is proved that the corresponding network design problem is NP-hard even for a single commodity and for single-element failures. The proof is based on the reduction of the Hamiltonian path problem.