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.
19021187
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. 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(mlog’n) time. This algorithm uses a recent dynamic connectivity algorithm and an old result of K&zig characterizing unique perfect matchings in terms of bridges. Also, given one perfect matching, we can test for the existence of another in linear time. This algorithm is a modification of Edmonds’ blossom-shrinldng algorithm implemented using depthfirst search. We prove a generalization of K&zig’s the+ rem characterizing unique f-factors in terms of bridges. This theorem allows us to give a modification of the frst algorithm that tests whether a given graph has a unique f-factor, and lind 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 mntcting. The method is an extension of OUT 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.
1829912
The Planar Hamiltonian Circuit Problem is NP-Complete
We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.
206562722
Dominating Sets in Planar Graphs
Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we wish to find the smallestesuch that, fornsufficiently large, everyn-vertex planar graph contains a dominating set of size at mosten.We prove that 1/4<e<1/3, and we conjecture thate=1/4.For triangulated discs we obtain a tight bound ofe=1/3.The upper bound proof yields a linear-time algorithm for finding an(n/3)-size dominating set.
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
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.
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.
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.
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.