8939316
A linear-time algorithm for finding an ambitus
We devise a linear-time algorithm for finding an ambitus ín an undirected graph. An ambitus is a cycle in a graph containing two distinguished vertices such that certain different groups of bridges (calledBitp-,BitQ-, andBitPQ-bridges) satisfy the property that a bridge in one group does not interlace with any bridge in the other groups. Thus, an ambitus allows the graph to be cut into pieces, where, in each piece, certain graph properties may be investigated independently and recursively, and then the pieces can be pasted together to yield information about these graph properties in the original graph. In order to achieve a good time-complexity for such an algorithm employing the divide-and-conquer paradigm, it is necessary to find an ambitus quickly. We also show that, using ambitus, linear-time algorithms can be devised for abiding-path-finding and nonseparating-induced-cycle-finding problems.
39925472
Unique Maximum Matching Algorithms
We consider the problem of testing the uniqueness of maximum matchings, both in the unweighted and in the weighted case. For the unweighted case, we have two results. First, given a graph with n vertices and m edges, we can test whether the graph has a unique perfect matching, and find it if it exists, in O(mlog4n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of Kotzig characterizing unique perfect matchings in terms of bridges. For the special case of planar graphs, we improve the algorithm to run in O(nlogn) time. Second, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds' blossom-shrinking algorithm implemented using depth-first search. A generalization of Kotzig's theorem proved by Jackson and Whitty allows us to give a modification of the first algorithm that tests whether a given graph has a unique f-factor, and find it if it exists. We also show how to modify the second algorithm to check whether a given f-factor is unique. Both extensions have the same time bounds as their perfect matching counterparts. For the weighted case, we can test in linear time whether a maximum-weight matching is unique, given the output from Edmonds' algorithm for computing such a matching. The method is an extension of our algorithm for the unweighted case.
204987180
Decomposition by clique separators
Abstract We consider the problem of decomposing a graph by means of clique separators, by which we mean finding cliques (complete graphs) whose removal disconnects the graph. We give an O( nm )-time algorithm for finding a decomposition of an n -vertex, m -edge graph. We describe how such a decomposition can be used in divide-and-conquer algorithms for various graph problems, such as graph coloring and finding maximum independent sets. We survey classes of graphs for which such divide-and-conquer algorithms are especially useful.
44984412
A Note on Finding the Bridges of a Graph
ly, algorithms havg been developed which 4Irst search to test various connectivity proof gzpks efficiently. Examples include algod9 find the wnnected, biconnected, and tricon; components of an undirected graph [l-3], the strongi> connected components 123 and domors [4] of a =dLected graph. Depth-first search is n0t &ways necessary for testing connectivity properthese efkiently, however. This note presents ent algorithm which uses any search method to And all the bridges of a graph. A gmph C = Cv,, e) is a set of vertices39 and a set of edges ~5. The edges are either unordered pairs (v, w) or distinc; vertices (the graph Is tial+eccieu~ or ordered pain (P? tr?ll) of distinct vertices (the graph isdkected). We denote the number of vertices by Vand the nurtther of edges by E. Graph G, = fc191,& 1) is a subgraph w’ G if”“? (vi, Q), t c cp’ and e I G.lf. A sequence of edges 5, vg), l *, fv,l, vn) is a puth from vl Co . A path is &zpl’e if all its vertices are distinct. There path of no edges from any vertex to itself. An un&tied graph is csnmt ted if there is a path between every pak of vertices. If there is a path from a vertex ~16flz vertex w in G but every path frt?m u to w con*&% edge e, then e is said to be a brki,{e of G. An undirected graph is Zridge-cunnected if i:: is connected and has no bridges. The connected (bridge-connected) components of a graph are its maxin% connected (bridgeconnected) szbgraphs.
12044793
Edge-disjoint spanning trees and depth-first search
SummaryThis paper presents an algorithm for finding two edge-disjoint spanning trees rooted at a fixed vertex of a directed graph. The algorithm uses depthfirst search and an efficient method for computing disjoint set unions. It requires O (eα(e, n)) time and O(e) space to analyze a graph with n vertices and e edges, where α (e, n) is a very slowly growing function related to a functional inverse of Ackermann's function.
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 ).
37146522
Making Data Structures Persistent
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.
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.
10887766
Fully persistent lists with catenation
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log log k) time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.
7483054
A Linear-Time Algorithm for a Special Case of Disjoint Set Union
This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in O(m+n) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in O(mα(m+n, n)+n) time and O(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving several other problems, including two-processor scheduling, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining the fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings in nonbipartite graphs.