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.     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

Fast parallel graph searching with applications

This paper presents fast parallel algorithms for the following graph theoretic problems: breadth-depth search of directed acyclic graphs; minimum-depth search of graphs; finding the minimum-weighted paths between all node-pairs of a weighted graph and the critical activities of an activity-on-edge network. The first algorithm hasO(logdlogn) time complexity withO(n ³) processors and the remaining algorithms achieveO(logd loglogn) time bound withO(n ²[n/loglogn]) processors, whered is the diameter of the graph or the directed acyclic graph (which also represents an activity-on-edge network) withn nodes. These algorithms work on an unbounded shared memory model of the single instruction stream, multiple data stream computer that allows both read and write conflicts.     

A separator theorem for graphs of bounded genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

Finding minimal nested polygons

An algorithm for finding a polygon with minimum number of edges nested in two simplen-sided polygons is presented. The algorithm solves the problem in at mostO(n logn) time, and improves the time complexity of two previousO(n ²) algorithms.The work was supported by NSERC grant OPG0041629.     

Maximum weight independent set in trees

Computing a maximum independent set, weighted or unweighted, isNP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum weight independent set in trees. A divide and conquer approach based on centroid decomposition of trees is used to compute a maximum weight independent set withinO(n logn) time, wheren is the number of vertices in the tree. We introduce a notion of analternating tree which is crucial in obtaining a new independent set from the previous one.     

A divide-and-conquer algorithm for constructing relative neighborhood graph

AnO(n logn) divide-and-conquer algorithm for finding the relative neighborhood graph RNG(V) of a set V ofn points in Euclidean space is presented. If implemented in parallel, its time complexity isO(n) and it requiresO(logn) processors.     

On-line coloring of perfect graphs

Lovász, Saks, and Trotter showed that there exists an on-line algorithm which will color any on-linek-colorable graph onn vertices withO(nlog^(2k–3) n/log^(2k–4) n) colors. Vishwanathan showed that at least (log ^k–1 n/k ^k ) colors are needed. While these remain the best known bounds, they give a distressingly weak approximation of the number of colors required. In this article we study the case of perfect graphs. We prove that there exists an on-line algorithm which will color any on-linek-colorable perfect graph onn vertices withn ^10k/loglogn colors and that Vishwanathan's techniques can be slightly modified to show that his lower bound also holds for perfect graphs. This suggests that Vishwanathan's lower bound is far from tight in the general case.Research partially supported by Office of Naval Research grant N00014-90-J-1206.     

Approximating maximum independent sets by excluding subgraphs

An approximation algorithm for the maximum independent set problem is given, improving the best performance guarantee known toO(n/(logn)²). We also obtain the same performance guarantee for graph coloring. The results can be combined into a surprisingly strongsimultaneous performance guarantee for the clique and coloring problems.The framework ofsubgraph-excluding algorithms is presented. We survey the known approximation algorithms for the independent set (clique), coloring, and vertex cover problems and show how almost all fit into that framework. We show that among subgraph-excluding algorithms, the ones presented achieve the optimal asymptotic performance guarantees.A preliminary version of this paper appeared in [9].Supported in part by National Science Foundation Grant CCR-8902522 and PYI Award CCR-9057488.Research done at Rutgers University. Supported in part by Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) fellowship.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

On a proposed divide-and-conquer minimal spanning tree algorithm

In a recent paper published in this journal, R. Chang and R. Lee purport to devise anO(N logN) time minimal spanning tree algorithm forN points in the plane that is based on a divide-and-conquer strategy using Voronoi diagrams. In this brief note, we present families of problem instances to show that the Chang-Lee worst-case timing analysis is incorrect, resulting in a time bound ofO(N ² logN). Since it is known that alternate, trulyO(N logN) time algorithms are available anyway, the general utility of the Chang-Lee algorithm is questionable.This author's research is supported in part by the Washington State Technology Center and by the National Science Foundation under grants ECS-8403859 and MIP-8603879.     

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.     

Low-diameter graph decomposition is in NC

We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log⁵(n)) time, and uses O(n²) processors. © 1994 John Wiley & Sons, Inc.     

Factoring matrices with a tree-structured sparsity pattern

Let A be a matrix whose sparsity pattern is a tree with maximal degree d_max. We show that if the columns of A are ordered using minimum degree on |A|+|A|^∗, then factoring A using a sparse LU with partial pivoting algorithm generates only O(d_maxn) fill, requires only O(d_maxn) operations, and is much more stable than LU with partial pivoting on a general matrix. We also propose an even more efficient and just-as-stable algorithm called sibling-dominant pivoting. This algorithm is a strict partial pivoting algorithm that modifies the column preordering locally to minimize fill and work. It leads to only O(n) work and fill. More conventional column pre-ordering methods that are based (usually implicitly) on the sparsity pattern of |A|^∗|A| are not as efficient as the approaches that we propose in this paper.     

Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Reconstructing visible regions from visible segments

An algorithm is presented for reconstructing visible regions from visible edge segments in object space. This has applications in hidden surface algorithms operating on polyhedral scenes and in cartography. A special case of reconstruction can be formulated as a graph problem: Determine the faces of a straight-edge planar graph given in terms of its edges. This is accomplished inO(n logn) time using linear space for a graph withn edges, and is worst-case optimal. The graph may have separate components but the components must not contain each other. The general problem of reconstruction is then solved by applying our algorithm to each component in the containment relation.Research of this author is supported by the National Science Foundation under grant no. ECS-8351942, and by the Schlumberger-Doll Research Labs, Ridgefield, Connecticut.     

A note on the largest empty rectangle problem

We consider the following problem: given a rectangle containingn points, find the largest perimeter subrectangle whose sides are parallel to those of the original rectangle, whose aspect ratio is below a given bound, and which does not contain any of the given points. Chazelle, Drysdale and Lee have studied a variant of this problem with areas as the quantity to be maximized. They gave anO(nlog³ n) algorithm for that problem. We adopt a similar divide-and-conquer approach and are able to use the simpler properties of the perimeter measure to obtain anO(nlog² n) algorithm for our problem.The work of the first author was supported by the Academy of Finland and that of the second by the Natural Sciences and Engineering Research Council of Canada Grant No. A-5692.