A polynomial time primal network simplex algorithm for minimum cost flows

Developing a polynomial time primal network simplex algorithm for the minimum cost flow problem has been a long standing open problem. In this paper, we develop one such algorithm that runs in O(min(n ²m lognC, n ²m² logn)) time, wheren is the number of nodes in the network,m is the number of arcs, andC denotes the maximum absolute arc costs if arc costs are integer and ∞ otherwise. We first introduce a pseudopolynomial variant of the network simplex algorithm called the “premultiplier algorithm”. We then develop a cost-scaling version of the premultiplier algorithm that solves the minimum cost flow problem in O(min(nm lognC, nm ² logn)) pivots. With certain simple data structures, the average time per pivot can be shown to be O(n). We also show that the diameter of the network polytope is O(nm logn).     

A new strongly polynomial dual network simplex algorithm

This paper presents a new dual network simplex algorithm for the minimum cost network flow problem. The algorithm works directly on the original capacitated network and runs in O(mn(m +n logn) logn) time for the network withn nodes andm arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos’ (1993) dual network simplex algorithm by a factor ofm/n.     

A new pivot selection rule for the network simplex algorithm

We present a new network simplex pivot selection rule, which we call theminimum ratio pivot rule, and analyze the worst-case complexity of the resulting network simplex algorithm. We consider networks withn nodes,m arcs, integral arc capacities and integral supplies/demands of nodes. We define a {0, 1}-valued penalty for each arc of the network. The minimum ratio pivot rule is to select that eligible arc as the entering arc whose addition to the basis creates a cycle with the minimum cost-to-penalty ratio. We show that the so-defined primal network simplex algorithm solves minimum cost flow problem within O(nΔ) pivots and in O(Δ(m + n logn)) time, whereΔ is any upper bound on the sum of all arc flows in every feasible flow. For assignment and shortest path problems, our algorithm runs in O(n ²) pivots and O(nm +n ² logn) time.     

A strongly polynomial algorithm for the transportation problem

For the (linear) transportation problem withm supply nodes,n demand nodes andk feasible arcs we describe an algorithm which runs in time proportional tom logm(k + n logn) (assuming w.l.o.g.mn). The algorithm uses excess scaling. The complexity bound is a slight improvement over the bound achieved by an application of a min-cost-flow algorithm of Orlin to the transportation problem.Corresponding author. Research supported in part by grant no. I-84-095.06/88 of the German—Israeli-Foundation for Scientific Research and Development.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

A polynomial dual simplex algorithm for the generalized circulation problem

This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m ²(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem. Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Polynomial dual network simplex algorithms

We show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. Our best pivoting strategy leads to an O(m ² logn) bound on the number of pivots, wheren andm denotes the number of nodes and arcs in the input network. If the demands are integral and at mostB, we also give an O(m(m+n logn) min(lognB, m logn))-time implementation of a strategy that requires somewhat more pivots.Research supported by AFOSR-88-0088 through the Air Force Office of Scientific Research, by NSF grant DOM-8921835 and by grants from Prime Computer Corporation and UPS.Research supported by NSF Research Initiation Award CCR-900-8226, by U.S. Army Research Office Grant DAAL-03-91-G-0102, and by ONR Contract N00014-88-K-0166.Research supported in part by a Packard Fellowship, an NSF PYI award, a Sloan Fellowship, and by the National Science Foundation, the Air Force Office of Scientific Research, and the Office of Naval Research, through NSF grant DMS-8920550.     

An efficient algorithm to solve connectivity problem on trapezoid graphs

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn ^1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n ²) time andO(n) space for a trapezoid graph.     

An O(mn log (nU)) time algorithm to solve the feasibility problem

The phase I maximum flow and most positive cut methods are used to solve the feasibility problem. Both of these methods take one maximum flow computation. Thus the feasibility problem can be solved using maximum flow algorithms. Let n and m be the number of nodes and arcs, respectively. In this paper, we present an algorithm to solve the feasibility problem with integer lower and upper bounds. The running time of our algorithm is O(mn log (nU)), where U is the value of maximum upper bound. Our algorithm improves the O(m² log (nU))-time algorithm in [12]. Hence the current algorithm improves the running time in [12] by a factor of n. Sleator and Goldberg’s algorithm is one of the well-known maximum flow algorithms, which runs in O(mn log n) time, see [5]. Under similarity assumption [11], our algorithm runs in O(mn log n) time, which is the running time of Sleator and Goldberg’s algorithm. The merit of our algorithm is that, in the case of infeasibility of the given network, it not only diagnoses infeasibility but also presents some information that is useful to modeler in estimating the maximum cost of adjusting the infeasible network.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

Finding minimum-cost flows by double scaling

Several researchers have recently developed new techniques that give fast algorithms for the minimum-cost flow problem. In this paper we combine several of these techniques to yield an algorithm running in O(nm(log logU) log(nC)) time on networks withn vertices,m edges, maximum arc capacityU, and maximum arc cost magnitudeC. The major techniques used are the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of Goldberg and Tarjan, and the dynamic tree data structure of Sleator and Tarjan. For nonsparse graphs with large maximum arc capacity, we obtain a similar but slightly better bound. We also obtain a slightly better bound for the (noncapacitated) transportation problem. In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.Research partially supported by an NSF Presidential Young Investigator Fellowship, Contract 8451517ECS, and grants from Analog Devices, Apple Computer Inc., and Prime Computer.On leave from Indian Institute of Technology, Kanpur, India.Research partially supported by an NSF Presidential Young Investigator Award.Research at Princeton University partially supported by National Science Foundation Grant DCR-8605962 and Office of Naval Research Contract N00014-87-K-0467.     

A random 1-011-011-01algorithm for depth first search

In this paper we present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithm is anRNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on aP-RAM. The run time of the algorithm isO(T _MM(n) log³ n), and the number of processors used isP _MM (n) whereT _MM(n) andP _MM(n) are the time and number of processors needed to find a minimum weight perfect matching on ann vertex graph with maximum edge weightn.This research was done while the first author was visiting the Mathematical Research Institute in Berkeley. Research supported in part by NSF grant 8120790.Supported by Air Force Grant AFOSR-85-0203A.     

A sublogarithmic convex hull algorithm

We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn ^1/3 divide-and-conquer and uses a simple pointer-based data structure.Part of this work was done when the last three authors were at the Department of Computer and Information Science, Linköping University. The research of the second author was supported by the Academy of Finland.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

Efficient algorithms to compute all articulation points of a permutation graph

Based on the geometric representation, an efficient algorithm is designed to find all articulation points of a permutation graph. The proposed algorithm takes onlyO(n logn) time andO(n) space, wheren represents the number of vertices. The proposed sequential algorithm can easily be implemented in parallel which takesO(logn) time andO(n) processors on an EREW PRAM. These are the first known algorithms for the problem on this class of graph.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.