18350108
Faster scaling algorithms for general graph matching problems
An algorithm for minimum-cost matching on a general graph with integral edge costs is presented. The algorithm runs in time close to the fastest known bound for maximum-cardinality matching. Specifically, let n, m, and N denote the number of vertices, number of edges, and largest magnitude of a cost, respectively. The best known time bound for maximum-cardinal ity matching M 0( Am). The new algorithm for minimum-cost matching has time bound 0( in a ( m, n )Iog n m log ( nN)). A slight modification of the new algorithm finds a maximum-cardinality matching in 0( fire) time. Other applications of the new algorlthm are given, mchrding an efficient implementa- tion of Christofides' traveling salesman approximation algorithm and efficient solutions to update problems that require the linear programming duals for matching.
18699794
Almost-optimum speed-ups of algorithms for bipartite matching and related problems
We present algorithms for matching and related problems that run on an EREW PRAM with <italic>p</italic> processors. Given is a bipartite graph <italic>G</italic> with <italic>n</italic> vertices, <italic>m</italic> edges, and integral edge costs at most <italic>N</italic> in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in <italic>&Ogr;</italic>(√<italic>nm</italic> log (<italic>nN</italic>)(log(2<italic>p</italic>))/<italic>p</italic>) time and <italic>&Ogr;</italic>(<italic>m</italic>) space, for <italic>p</italic> ≤ <italic>m</italic>/(√<italic>n</italic>log<supscrpt>2</supscrpt><italic>n</italic>). For <italic>p</italic> = 1 this improves the best known sequential algorithm, and is within a factor of log (<italic>nN</italic>) of the best known bound for the problem without costs (maximum cardinality matching). For <italic>p</italic> > 1 the time is within a factor of log <italic>p</italic> of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.
35743828
Transitive Compaction in Parallel via Branchings
Abstract We study the following problem: given a strongly connected digraph, find a minimal strongly connected spanning subgraph of it. Our main result is a parallel algorithm for this problem, which runs in polylog parallel time and uses O ( n 3 ) processors on a PRAM. Our algorithm is simple and the major tool it uses is computing a minimum-weight branching with zero-one weights. We also present sequential algorithms for the problem that run in time O ( m + n · log n ).
31445898
Enumeration of the Elementary Circuits of a Directed Graph
An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied to a graph with $V$ vertices, $E$ edges, and $C$ elementary circuits. Keywords: Algorithm, circuit, cycle, graph
52152408
A new approach to the maximum-flow problem
All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the <italic>preflow</italic> concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an <italic>O</italic>(<italic>n</italic><supscrpt>3</supscrpt>) time bound on an <italic>n</italic>-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in <italic>O</italic>(<italic>nm</italic> log(<italic>n</italic><supscrpt>2</supscrpt>/<italic>m</italic>)) time on an <italic>n</italic>-vertex, <italic>m</italic>-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>log <italic>n</italic>) time using <italic>n</italic> processors and <italic>O</italic>(<italic>m</italic>) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses <italic>n</italic> processors but requires <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>) space.
37146522
Making Data Structures Persistent
6385041
Maintenance of a minimum spanning forest in a dynamic planar graph
Abstract : We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and insertion and deletion of edges and vertices. To implement the algorithms, we develop a data structure called an edge-ordered dynamic tree, which is a variant of the dynamic tree data structure of Sleator and Tarjan. Using this data structure, our algorithms run in O(log n) time per operation and O(n) space. The algorithms can be used to maintain the connected components of a dynamic planar graph in O(log n) time per operation.