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 parallel graph edge matching algorithm and its applications

A fast and efficient parallel algorithm for finding a maximal edge matching in an undirected graphG(V,E) is proposed.It runs in O(log n)time with O(m,/log n n)processors on an EREW PRAM for a class of graph set П,where n=|V|,m=|E|and П includes at least (i)planar graphs;(ii) graphs of bounded genus;and (iii)graphs of bounded maximum degress and so on.Our algorithm improves the previously known best algorithms by a factor of logn in the time complexity with linear number of processors on EREW PRAMs when the input is limited to П.     

图论中最大独立集问题的精确算法

独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为[O(1.285n)]的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。     

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.     

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.     

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.     

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 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.     

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 algorithm for computing object poses in a modular fixture or gripper

Modular or reconfigurable fixtures (or grippers) can reduce manufacturing costs and time remarkably. Computing the poses of a given object in a modular fixture is a basic but tedious technique for designing and using such fixtures. This article presents an efficient algorithm for computing the poses. Starting from a unified expression of the outline of an object, this algorithm searches all matching poses automatically. If the outline consists of straight lines and circular arcs only, all the unknown variables can be calculated sequentially by substituting known (or tentative) data in respective expressions, without solving complicated simultaneous equations. When applied to arbitrary outlines, it involves nothing more than common interpolation. The search process is visualized through diagrams that clearly display the occurrence of matching poses. The computer programs are universally applicable. Only the data of the object outline and the fixture configuration need be input. Case studies show that the programs run fast and yield accurate results. © 2002 Wiley Periodicals, Inc.     

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 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.     

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.