Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the aww vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure array A^* of an undirected graph.The time complexity of the parallel algorithm is O(n^3/p).If D,P and A^* are known,it is shown that the problems to find all connected components,to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p logp)time.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and unicycular graphs. Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.Part of this work was done while the first author was at the University of Illinois, Urbana-Champaign, the second author was at Carnegie-Mellon University, and the third author was at the Hebrew University and the Courant Institute of Mathematical Sciences, New York University. A preliminary version of this work was presented at the 1986 International Conference on Parallel Processing.     

Efficient parallel algorithms for graph problems

We present an efficient technique for parallel manipulation of data structures that avoids memory access conflicts. That is, this technique works on the Exclusive Read/Exclusive Write (EREW) model of computation, which is the weakest shared memory, MIMD machine model. It is used in a new parallel radix sort algorithm that is optimal for keys whose values are over a small range. Using the radix sort and known results for parallel prefix on linked lists, we develop parallel algorithms that efficiently solve various computations on trees and “unicycular graphs.” Finally, we develop parallel algorithms for connected components, spanning trees, minimum spanning trees, and other graph problems. All of the graph algorithms achieve linear speedup for all but the sparsest graphs.     

Recursion and parallel algorithms in geometric modeling problems

An efficient approach to the accurate computer modeling of phenomena and processes is discussed. The “divide-and-conquer” technique is used to develop a generalized parallel-recursive algorithm for simultaneous solution of a collection of interrelated problems that use a common unified data structure (weighted concatenable queue) at the merge stage. The decomposition stage is common and is executed only once for all tasks. These means are efficient and convenient for constructing and studying complex computational models.     

Efficient parallel solution of structural eigenvalue problems

An efficient parallelisation of an existing sequential method for obtaining the eigenvalues of a structure by an exact analytical procedure is presented. Results are given which illustrate finding the undamped natural frequencies of a rigidly jointed plane frame, but the method is also applicable to buckling problems and to other types of structure. The parallel method is suited to both distributed and shared-memory parallel machines. It seeks to equate the workload of each processor (node) by initially sharing out the work and by subsequently passing work from working nodes to idle nodes. Experimental runs on an nCUBE2 computer show that reasonably high levels of efficiency are possible.     

Dynamics and solutions to some control problems for water-tanksystems

We consider a tank containing a fluid. The tank is subjected to directly controlled translations and rotations. The fluid motion is described by linearized wave equations under shallow water approximations. For irrotational flows, a new variational formulation of Saint-Venant equations is proposed. This provides a simple method to establish the equations when the tank is moving. Several control configurations are studied: one and two horizontal dimensions; tank geometries (straight and nonstraight bottom, rectangular and circular shapes), tank motions (horizontal translations with and without rotations). For each configuration, we prove that the linear approximation is steady-state controllable and provide a simple and flatness-based algorithm for computing the steering open-loop control. These algorithms rely on operational calculus. They lead to second order equations in space variables whose fundamental solutions define delay operators corresponding to convolutions with compact support kernels. For each configuration, several controllability open-problems are proposed and motivated     

Efficient parallel algorithms for path problems in directed graphs

In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log² n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.     

Efficient parallel algorithms for path problems in directed graphs

In this paper we describe a technique for finding efficient parallel algorithms for problems on directed graphs that involve checking the existence of certain kinds of paths in the graph. This technique provides efficient algorithms for finding dominators in flow graphs, performing interval and loop analysis on reducible flow graphs, and finding the feedback vertices of a digraph. Each of these algorithms takesO(log² n) time using the same number of processors needed for fast matrix multiplication. All of these bounds are for an EREW PRAM.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.     

Fair solutions for some multiagent optimization problems

We consider optimization problems in a multiagent setting where a solution is evaluated with a vector. Each coordinate of this vector represents an agent’s utility for the solution. Due to the possible conflicts, it is unlikely that one feasible solution is optimal for all agents. Then, a natural aim is to find solutions that maximize the satisfaction of the least satisfied agent, where the satisfaction of an agent is defined as his relative utility, i.e., the ratio between his utility for the given solution and his maximum possible utility. This criterion captures a classical notion of fairness since it focuses on the agent with lowest relative utility. We study worst-case bounds on this ratio: for which ratio a feasible solution is guaranteed to exist, i.e., to what extend can we find a solution that satisfies all agents? How can we build these solutions in polynomial time? For several optimization problems, we give polynomial-time deterministic algorithms which (almost always) achieve the best possible ratio.     

Efficient parallel recognition of some circular arc graphs,I

We present the first efficient parallel algorithms for recognizing some subclasses of circular arc graphs including circular arc graphs and proper interval graphs. These algorithms run in O(log² n) time withO(n ³) processors on a CRCW PRAM. An intersection representation can also be constructed within the same resource bounds. Furthermore, we propose some new characterizations of circular arc graphs and proper interval graphs.Portions of this paper have appeared in preliminary form in theProceedings of the 1989 IEEE international Symposium on Circuits and Systems [9], theProceedings of the 1989 Workshop on Algorithms and Data Structures [10], and theProceedings of the 1990 Canadian Conference on Computational Geometry [11].     

Efficient parallel recognition of some circular arc graphs, II

Based on Tucker's work, we present an accurate proof of the characterization of proper circular arc graphs and obtain the first efficient parallel algorithm which not only recognizes proper circular arc graphs but also constructs proper circular arc representations. The algorithm runs inO(log² n) time withO(n ³) processors on a Common CRCW PRAM. The sequential algorithm can be implemented to run inO(n ²) time and is optimal if the input graph is given as an adjacency matrix, so to speak. Portions of this paper appear in preliminary form in theProceedings of the 1989Workshop on Algorithms and Data Structures [2], and theProceedings of the 1994International Symposium on Algorithms and Computation [5].     

Exact solutions to some minimum time problems with inequality state constraints

A heuristic method is developed for generating exact solutions to certain minimum time problems, with inequality state and control constraints. The control equation is linear and autonomous, with scalar-valued control. The state constraints are also linear inequalities. Assuming knowledge of a finite sequence, in which state and/or control constraints become active along an optimal path, the maximum principle is reduced to a set of equations and inequalities in a finite number of unknowns. A solution to the equations and inequalities determines both the solution path and a proof of its optimality. Certain types of constraint sequences lead to overdetermined equation systems, and this fact is interpreted in terms of the qualitative behavior of solutions to these problems. Two path-planning problems are solved, as illustrations of the solution technique.     

Exact solutions to some minimum-time problems and their behaviornear inequality state constraints

A heuristic method for generating exact solutions to certain minimum-time problems with inequality state constraints is used to generate solutions to a class of path-planning problems. It is observed that, when the state constraint function has a continuous second derivative, the constraint does not become active for any continuous-time period. Instead, the solution bumps up against the constraint repeatedly at isolated points. The solution method offers some insight into this behavior. It is shown that such a state constraint can become active for a continuous-time period only if the solution path satisfies an overdetermined system of equations. It is argued that the phenomenon is general and will arise in many different optimization problems     

Globally optimal benchmark solutions to some small-scale discretized continuum topology optimization problems

In this note, globally optimal solutions to three sets of small-scale discretized continuum topology optimization problems are presented. All the problems were discretized by the use of nine-node isoparametric finite elements. The idea is that these solutions can be used as benchmark problems when testing new algorithms for finding pure 0–1 solutions to topology optimization problems defined on discretized ground structures.     

Exact solutions of some optimization problems of transport logistics

A problem for constructing the shortest cyclic route that ensures homogeneous cargo is delivered from producers to consumers by a transport vehicle of limited capacity is considered. Formalizations in the form of Boolean quadratic programming and linear integer programming problems are given. Comparative analysis of the efficiency of three exact algorithms is performed. The problem of finding the minimal admissible capacity of the transport vehicle is considered as an auxiliary problem. Dependence of the length of the optimal route on the capacity of the transport vehicle is studied experimentally.