11724969
Finding a Maximum Independent Set
We present an algorithm which finds a maximum independent set in an n-vertex graph in 0($2^{n/3}$) time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.
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.
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.
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 ).
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.
705851
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 <italic>m</italic> union and find operations on <italic>n</italic> elements in 0(<italic>m</italic>+<italic>n</italic>) time and 0(<italic>n</italic>) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in 0(<italic>m</italic>α(<italic>m</italic>+<italic>n, n</italic>)+<italic>n</italic>) time and 0(<italic>n</italic>) space, where α is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving a number of other problems, including two-processor scheduling, the off-line min problem, 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 a 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 on nonbipartite graphs.
364871
Making data structures persistent
Abstract This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and efficient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O (1) space bounds for insertion and deletion.
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.
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