The maximum flow problem is one of the most common network flow problems. This problem involves finding the maximum possible amount of flow between two designated nodes on a network with arcs having flow capacities. T...
详细信息
The maximum flow problem is one of the most common network flow problems. This problem involves finding the maximum possible amount of flow between two designated nodes on a network with arcs having flow capacities. The push-relabel algorithm is one of the fastest algorithms to solve this problem. We present a shared memory parallel push-relabel algorithm. Graph coloring is used to avoid collisions between threads for concurrent push and relabel operations. In addition, excess values of target nodes are updated using atomic instructions to prevent race conditions. The experiments show that our algorithm is competitive for wide graphs with low diameters. Results from three different data sets are included, computer vision problems, DIMACS challenge problems, and KaHIP partitioning problems. These are compared with existing push-relabel and pseudoflow implementations. We show that high speedup rates are possible using our coloring based parallelization technique on sparse networks. However, we also observe that the pseudoflow algorithm runs faster than the push-relabel algorithm on dense and long networks.
We consider the problem of finding a feasible flow in a directed network G = (N,A) in which each node i is an element of N has a supply b(i), and each are (i,j) is an element of A has a zero lower bound on flow and an...
详细信息
We consider the problem of finding a feasible flow in a directed network G = (N,A) in which each node i is an element of N has a supply b(i), and each are (i,j) is an element of A has a zero lower bound on flow and an upper bound u(ij). It is well known that this feasibility problem can be transformed into a maximum flow problem. It is also well known that there is no feasible how in the network G if and only if there is a subset S of nodes such that the net supplies of the nodes in S exceeds the capacity of the arcs emanating from S. Such a set S is called a "witness of infeasibility" (or, simply, a witness) of the network flow problem. In the case that there are many different witnesses for an infeasible problem, a small cardinality witness may be preferable in practice because it is generally easier for the user to assimilate, and may provide more guidance to the user on how to identify the cause of the infeasibility. Here we show that the problem of finding a minimum cardinality witness is NP-hard. We also consider the problem of determining a minimal witness, that is, a witness S such that no proper subset of S is also a witness. In this paper, we show that we can determine a minimal witness by solving a sequence of at most n maximum flow problems. Moreover, if we use the preflow-push algorithm to solve the resulting maximum flow problems and organize computations properly, then the total time taken by the algorithm is comparable to that of solving a single maximum flow problem. This approach determines a minimal cardinality witness in O(n(2)m(1/2)) time using simple data structures and in O(nm log n) time using the standard implementation of the dynamic tree data structures. We also show that the recognition version of the minimal witness problem is equivalent to a recognition version of a related problem known as the minimum rooted cut problem. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
暂无评论