Optimal parallel algorithms for multiple updates of minimum spanning trees

Parallel updates of minimum spanning trees (MSTs) have been studied in the past. These updates allowed a single change in the underlying graph, such as a change in the cost of an edge or an insertion of a new vertex. Multiple update problems for MSTs are concerned with handling more than one such change. In the sequential case multiple update problems may be solved using repeated applications of an efficient algorithm for a single update. However, for efficiency reasons, parallel algorithms for multiple update problems must consider all changes to the underlying graph simultaneously. In this paper we describe parallel algorithms for updating an MST whenk new vertices are inserted or deleted in the underlying graph, when the costs ofk edges are changed, or whenk edge insertions and deletions are performed. For multiple vertex insertion update, our algorithm achieves time and processor bounds ofO(log n·logk) and nk/(logn·logk), respectively, on a CREW parallel random access machine. These bounds are optimal for dense graphs. A novel feature of this algorithm is a transformation of the previous MST andk new vertices to a bipartite graph which enables us to obtain the above-mentioned bounds.     

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

基于改进遗传算法的最小生成树算法

以图论和改进遗传算法为基础,提出了一种求最小生成树的遗传算法。该算法采用二进制表示最小树问题,并设计出相应的适应度函数、算子以及几种控制策略,以提高执行速度和进化效率。传统算法一次只能得到一个候选解。用该算法对其求解,可以在较短的时间内以较高的概率获得多个候选解。应用实例表明该算法优于传统算法。     

A parallel algorithm for the enumeration of the spanning trees of a graph

As is well known, the strategy of divide-and-conquer is widely used in problem solving. The method of partitioning is also a fundamental strategy for the design of a parallel algorithm. The problem of enumerating the spanning trees of a graph arises in several contexts such as computer-aided design and computer networks. A parallel algorithm for solving the problem is presented in this paper. It is based on the principle of the inclusion and exclusion of sets, and not directly based on the partitioning of the graph itself. The results of the preliminary experiments on a MIMD system appear promising.     

Efficient algorithms for (3, 1) graphs

In this paper, we define a class of graphs which are referred to as (3, 1) graphs. A graph is a member of this class if it has the property that within each set of three vertices, there is at least one edge. We derive a lower bound for the size of a maximum clique in a (3, 1) graph as well as an upper bound for the size of a minimum clique covering. In addition, we show that there exists a linear algorithm for constructing a Hamiltonian circuit in a connected (3, 1) graph and an n⁴-algorithm for finding a minimum coloring in a (3, 1) graph.     

There are planar graphs almost as good as the complete graphs and almost as cheap as minimum spanning trees

Let S be a set ofn points in the plane. For an arbitrary positive rationalr, we construct a planar straight-line graph onS that approximates the complete Euclidean graph onS within the factor (1 + 1/r)[2/3 cos(/6)], and it has length bounded by 2r + 1 times the length of a minimum Euclidean spanning tree onS. Given the Deiaunay triangulation ofS, the graph can be constructed in linear time.     

Parallel algorithms for minimal spanning trees of directed graphs

The main results of this paper are efficient parallel algorithms, MSP and LOCATE, for computing minimal spanning trees and locating minimal paths in directed graphs, respectively. Algorithm MSP has time complexityO(log³ n) usingO(n ³/logn) processors, while LOCATE has time complexityO(logn) usingO(n ²) processors. Algorithm MSP is derived from sequential algorithms, when the unbounded parallelism model is used.     

Efficient algorithms for single- and two-layer linear placement of parallel graphs

This paper outlines an algorithm for optimum linear ordering (OLO) of a weighted parallel graph with O(n log k) worst-case time complexity, and O(n + k log(n/k) log k) expected-case time complexity, where n is the total number of nodes and k is the number of chains in the parallel graph. Next, the two-layer OLO problem is considered, where the goal is to place the nodes linearly in two routing layers minimizing the total wire length. The two-layer problem is shown to subsume the maxcut problem and a befitting heuristic algorithm is proposed. Experimental results on randomly generated samples show that the heuristic algorithm runs very fast and outputs optimum solutions in more than 90% instances.     

Efficient approximation algorithms for shortest cycles in undirected graphs

We describe a simple combinatorial approximation algorithm for finding a shortest (simple) cycle in an undirected graph. Given an adjacency-list representation of an undirected graph G with n vertices and unknown girth k, our algorithm returns with high probability a cycle of length at most 2k for even k and 2k+2 for odd k, in time . Thus, in general, it yields a approximation. For a weighted, undirected graph, with non-negative edge weights in the range {1,2,…,M}, we present a simple combinatorial 2-approximation algorithm for a minimum weight (simple) cycle that runs in time O(n²logn(logn+logM)).     

Parallel breadth-first search algorithms for trees and graphs

Parallel Breadth-First Search (BFS) algorithms for ordered trees and graphs on a shared memory model of a Single Instruction-stream Multiple Data-stream computer are proposed. The parallel BFS algorithm for trees computes the BFS rank of eachnode of an ordered tree consisting of n nodes in time of 0(β log n) when 0(n ^1+1/β) processors are used, β being an integer greater than or equal to 2. The parallel BFS algorithm for graphs produces Breadth-First Spanning Trees (BFSTs) of a directedgraph G having n nodes in time 0(log d.log n) using 0(n ³) processors, where d is the diameter of G If G is a strongly connected graph or a connected undirected graph the BFS algorithm produces n BFSTs, each BFST having a different start node.     

Efficient parallel processing of competitive learning algorithms

Vector quantization (VQ) is an attractive technique for lossy data compression, which has been a key technology for data storage and/or transfer. So far, various competitive learning (CL) algorithms have been proposed to design optimal codebooks presenting quantization with minimized errors. Although algorithmic improvements of these CL algorithms have achieved faster codebook design than conventional ones, limitations of speedup still exist when large data sets are processed on a single processor. Considering a variety of CL algorithms, parallel processing on flexible computing environment, like general-purpose parallel computers is in demand for a large-scale codebook design. This paper presents a formulation for efficiently parallelizing CL algorithms, suitable for distributed-memory parallel computers with a message-passing mechanism. Based on this formulation, we parallelize three CL algorithms: the Kohonen learning algorithm, the MMPDCL algorithm and the LOJ algorithm. Experimental results indicate a high scalability of the parallel algorithms on three different types of commercially available parallel computers: IBM SP2, NEC AzusA and PC cluster.     

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexityO(f(n)/p+I(n)logn) on the PRAM usingp processors, whereI(n) is logn on the EREW PRAM, log logn on the CCRW PRAM,f(n) iso(n ³). On the randomized CRCW PRAM we are able to achieve time complexityO(n ³/p+logn) usingp processors. A preliminary version of this paper was presented at the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992. Support by NSF Grant CCR 90-20690 and PSC CUNY Awards #661340 and #662478.     

Efficient parallel algorithms for numerical simulation

COUPL+ is a programming environment for applications using unstructured and hybrid grids for numerical simulations. It automates parallelization by handling the partitioning of data and dependent data and maintaining halo interfaces and copy coherency. We explore some algorithms behind this package. A multi-level partitioning method is described which is effective in the presence of skewed data, solving the multi-set median-finding problem. Partitioning elements over a set of pre-partitioned nodes is explored and a novel method is suggested for reducing communication in the resulting distribution.     

Associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node to a graph

This paper proposes a new associative parallel algorithm for dynamic update of a minimum spanning tree after addition of a new node with all its incident edges to a graph. This algorithm is represented as the InsertVert procedure implemented on a model of an associative parallel system of the SIMD type with vertical processing (a STAR machine). The correctness of the procedure is proved and its time complexity is estimated. This work was supported by the Russian Foundation for Basic Research under grant 03-01-00399. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 19–31, January–February 2006.     

求解度约束最小生成树的新的快速算法

针对度约束最小生成树问题,提出了一种新的快速算法。新的快速算法分为两个主要部分,第一部分从一棵最小生成树出发,构造一棵度约束树。第二部分设计了一种改进策略,从第一部分求得的度约束树出发,每次去掉树的一条边,将顶点按照连通性划分成两个集合,在不违反度约束的情况下,从这两个集合构成的边割中,选择一条权值减少最大的边添加到图中。通过大量的数值实验表明新的快速算法性能良好。     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.