An efficient parallel algorithm for computing a large independent set in a planar graph

Let (G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set such that ¦I¦ (G)/2. The algorithm runs in timeOlog² n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed locally and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.Joseph Naor was supported by Contract ONR N00014-88-K-0166. Most of this work was done while he was a post-doctoral fellow at the Department of Computer Science, University of Southern California, Los Angeles, CA 90089-0782, USA.     

An output sensitive algorithm for computing a maximum independent set of a circle graph

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(nmin{d,α}) time at worst, for an n vertex circle graph where α is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Θ(nd) time at worst.     

An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

Optimal parallel algorithm for findingst-ambitus of a planar biconnected graph

A cycleC passing through two specific verticess andt of a biconnected graph is said to be anst-ambitus if its bridges do not interlace in some special way. We present algorithms forst-ambitus for planar biconnected graphs, which are much simpler than the one known for general graphs [MT]. Our algorithm runs inO(n) time on a sequential machine and (logn) parallel time usingO(n/logn) processors on an EREW PRAM.     

An efficient algorithm for parallel integer multiplication

In this paper we propose an efficient algorithm to implement parallel integer multiplication by a combination of parallel additions, shifts and reads from a memory-resident lookup table dedicated to squares. Such an operator called PIM (parallel integer multiplication) is in fact microprogrammed at the PROM level. Our theoretical approach is included within the framework of time and space parallel complexity theory. The mathematical relation used defines this multiplication operator in terms of a difference of two quadratic expressions, each being computed in parallel by one addition and one shift. This leads to the CPU time for any pair of numbers being constant. Our contribution is above all of practical interest on any massively parallel architecture in the field of scientific and numerical computing.     

An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.     

A fully parallel block independent set algorithm for distributed sparse matrices

We present a fully parallel algorithm for constructing block independent set for general sparse matrices in a distributed environment. The block independent set is used in the construction of parallel multilevel preconditioners in solving large sparse matrices on distributed memory parallel computers. We compare a few implementations of the parallel multilevel ILU preconditioners with different block independent set construction strategies. Numerical experiments indicate that the parallel block independent set algorithm is effective in reducing both the parallel multilevel preconditioner construction time and the size of the last level reduced system.     

An efficient parallel termination detection algorithm

In this paper, we present a new, easy to implement algorithm for detecting the termination of a parallel asynchronous computation on distributed-memory MIMD computers. We demonstrate that it operates concurrently with the main computation, adding minimal overhead, and we prove that it correctly detects termination when it occurs. Experimental results confirm that the termination detection routine imposes an overhead smaller than the experimental uncertainty.     

On the feedback vertex set problem for a planar graph

An algorithm solving the feedback-vertex-set problem for planar digraphs is described. In particular, planar graphs with a certain additional condition are considered as they arise from solving systems of linear equations obtained from convection-dominated flow problems. The proposed algorithm requires a computational work linear in the size of the graph. Furthermore, a side-product is a decomposition of the graph into subsets that are of interest for block-Gauß-Seidel smoothers in multi-grid methods.     

An efficient algorithm for computing permanental polynomials of graphs

An efficient numerical method for computing permanental polynomials of graphs is proposed. It adapts multi-entry expansion of FFT, and is parallel in nature. It is applied to fullerene-type graphs, and works for C₅₆, while the largest fullerene computed before is C₄₀. Extensive numerical computations show that the algorithm is fast and stable.     

Towards a portable and efficient environment for parallel computing

The availability of more and more cost-effective and powerful parallel computers has enhanced the ability of the operations research community to solve more laborious computational problems. In this paper an attempt has been made to implement a parallel simulation runs dispatcher with an objective to study the feasibility of establishing a portable and efficient parallel programming environment. This parallel simulation run dispatcher can be applied to both terminating type and steady-state type simulation models. The algorithm is then transferred and executed on various other shared-memory multiprocessor systems to illustrate its portability. Another contribution of this paper is to verify whether the performance of the portable code and the non-portable code of a same algorithm is significantly different on a specific parallel system using the analysis of covariance model.     

An efficient parallel algorithm for building the separating tree

We present an efficient parallel algorithm for building the separating tree for a separable permutation. Our algorithm runs in O(log²n)$O\left({log}^{2}n\right)$ time using O(nlog^1.5n)$O\left(n{log}^{1.5}n\right)$ operations on the CREW PRAM and O(log²n)$O\left({log}^{2}n\right)$ time using O(nlognloglogn)$O(nlognloglogn)$ operations on the COMMON CRCW PRAM.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

An efficient parallel recognition algorithm forbipartite-permutation graphs

We present a parallel recognition algorithm for bipartite-permutation graphs. The algorithm can be executed in O(log n) time on the CRCW PRAM if O(n³/log n) processors are used, or O(log² n) time on the CREW PRAM if O(n³/log² n) processors are used. Chen and Yesha (1993) have presented another CRCW PRAM algorithm that takes O(log²n) time if O(n ³) processors are used. Compared with Chen and Yesha's algorithm, our algorithm requires either less time and fewer processors on the same machine model, or fewer processors on a weaker machine model. Our algorithm can also be applied to determine if two bipartite-permutation graphs are isomorphic     

A parallel graph partitioning algorithm for a message-passing multiprocessor

We develop a parallel algorithm for partitioning the vertices of a graph intop2 sets in such a way that few edges connect vertices in different sets. The algorithm is intended for a message-passing multiprocessor system, such as the hypercube, and is based on the Kernighan-Lin algorithm for finding small edge separators on a single processor.⁽¹⁾ We use this parallel partitioning algorithm to find orderings for factoring large sparse symmetric positive definite matrices. These orderings not only reduce fill, but also result in good processor utilization and low communication overhead during the factorization. We provide a complexity analysis of the algorithm, as well as some numerical results from an Intel hypercube and a hypercube simulator.Publication of this report was partially supported by the National Science Foundation under Grant DCR-8451385 and by AT&T Bell Laboratories through their Ph.D scholarship program.     

An efficient parallel algorithm for the efficient domination problem on distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms for solving problems on distance-hereditary graphs. With an n-vertex and m-edge distance-hereditary graph G, we show that the efficient domination problem on G can be solved in O(log/sup 2/ n) time using O(n + m) processors on a CREW PRAM. Moreover, if a binary tree representation of G is given, the problem can be optimally solved in O(log n) time using O(n/log n) processors on an EREW PRAM.     

The relative neighbourhood graph of a finite planar set

The relative neighbourhood graph (RNG) of a set of n points on the plane is defined. The ability of the RNG to extract a perceptually meaningful structure from the set of points is briefly discussed and compared to that of two other graph structures: the minimal spanning tree (MST) and the Delaunay (Voronoi) triangulation (DT). It is shown that the RNG is a superset of the MST and a subset of the DT. Two algorithms for obtaining the RNG of n points on the plane are presented. One algorithm runs in 0(n²) time and the other runs in 0(n³) time but works also for the d-dimensional case. Finally, several open problems concerning the RNG in several areas such as geometric complexity, computational perception, and geometric probability, are outlined.     

An efficient distributed algorithm for detection of knots and cycles in a distributed graph

Knot detection in a distributed graph is an important problem and finds applications in deadlock detection in several areas such as store-and-forward networks, distributed simulation, and distributed database systems. This paper presents an efficient distributed algorithm to detect if a node is part of a knot in a distributed graph. The algorithm requires 2e messages and a delay of 2(d+1) message hops to detect if a node in a distributed graph is in a knot (here, e is the number of edges in the reachable part of the distributed graph and d is its diameter). A significant advantage of this algorithm is that it not only detects if a node is involved in a knot, but also finds exactly which nodes are involved in the knot. Moreover, if the node is not involved in a knot, but is only involved in a cycle, then it finds the nodes that are in a cycle with that node. We illustrate the working of the algorithm with examples. The paper ends with a discussion on how the information about the nodes involved in the knot can be used for deadlock resolution and also on the performance of the algorithm.