Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

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.     

An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs

In this paper, we solve the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs efficiently in parallel. Let T_d(|V|,|E|) and P_d(|V|,|E|) denote the parallel time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G=(V,E) on a PRAM model M_d. We show that this problem can be solved in O(T_d(|V|,|E|)+log|V|) time using O(P_d(|V|,|E|)+(|V|+|E|)/log|V|) processors on M_d. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(log|V|) time using O((|V|+|E|)/log|V|) processors on an EREW PRAM. We also obtain a linear-time algorithm which is faster than the previous known O(|V|³) sequential algorithm.     

计算两类网络的可靠性的多项式时间算法

定义了两类有向网络——ORC-网络和IRC-网络,并且提出一个计算它们的根通信可靠性(网络的一个特定结点(根点)能与其余每个结点通信的概率)的多项式时间算法.对于ORC-网络和IRC-网络,该算法的时间复杂度分别是O(｜E｜)和O(｜V｜·｜E｜),这里,｜V｜,｜E｜分别表示网络所含结点和边的数量.     

Minimum Cycle Bases for Network Graphs

The minimum cycle basis problem in a graph G = (V,E) is the task to construct a minimum length basis of its cycle vector space. A well-known algorithm by Horton of 1987 needs running time O(|V||E|^2.376). We present a new combinatorial approach which generates minimum cycle bases in time O(\max{|E|³,|E||V|²log |V|}) with a space requirement of (|E|²). This method is especially suitable for large sparse graphs of electric engineering applications since there, typically, |E| is close to linear in |V|.     

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 Linear Time Algorithm for the Arc Disjoint Menger Problem in Planar Directed Graphs

Given a graph G=(V,E) and two vertices s,t ∈ V , s\neq t , the Menger problem is to find a maximum number of disjoint paths connecting s and t . Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For planar graphs the edge disjoint Menger problem has been solved to optimality [W2], while the fastest algorithm for the arc disjoint version is Weihe's general maximum flow algorithm for planar networks [W1], which has running time \bf O (|V| log |V|) . Here we present a linear time, i.e., asymptotically optimal, algorithm for the arc disjoint version in planar directed graphs. Received August 1997; revised January 1999.     

Finding Euler tours in parallel

The problem of finding Euler tours in directed and undirected Euler graphs is considered. O(log |V|) time algorithms are given using a linear number of processors on a concurrent-read concurrent-write parallel RAM.     

A new distributed breadth-first-search algorithm

A new distributed breadth-first-search algorithm for graphs is presented. Its worst-case communication and time complexities are both O(|V|²), where |V| is the number of vertices. The existing algorithm, due to Cheung (1983), has communication and time complexities O(|V|³) and O(|V|), respectively.     

渐变填充的性质和算法

本文着重研究了Jordan数字流形上的渐变填充,设计了紧缩渐变填充算法和分裂渐变填充算法;并证明:如果D是离散网格空间上的Jordan凸集,那么存在O(|D||D|)时间的紧缩算法去做渐变填充.最后,我们对Jordan正方形区域、三角域和圆盘,分别给出了它们各自的O(|D|log_2|D|)时间的分裂渐变填充算法.     

Parallel Algorithms for Maximum Matching in Complements of Interval Graphs and Related Problems

Given a set of n intervals representing an interval graph, the problem of finding a maximum matching between pairs of disjoint (nonintersecting) intervals has been considered in the sequential model. In this paper we present parallel algorithms for computing maximum cardinality matchings among pairs of disjoint intervals in interval graphs in the EREW PRAM and hypercube models. For the general case of the problem, our algorithms compute a maximum matching in O( log ³ n) time using O(n/ log ² n) processors on the EREW PRAM and using n processors on the hypercubes. For the case of proper interval graphs, our algorithm runs in O( log n ) time using O(n) processors if the input intervals are not given already sorted and using O(n/ log n ) processors otherwise, on the EREW PRAM. On n -processor hypercubes, our algorithm for the proper interval case takes O( log n log log n ) time for unsorted input and O( log n ) time for sorted input. Our parallel results also lead to optimal sequential algorithms for computing maximum matchings among disjoint intervals. In addition, we present an improved parallel algorithm for maximum matching between overlapping intervals in proper interval graphs. Received November 20, 1995; revised September 3, 1998.     

高效的信息表求核算法——兄弟判断法

基于信息表的求核算法存在如下不足:需要完整求出U/R后方可求核.为此,先寻求理论依据,说明U/R与U/(R-{a})的内在关系,得出了[x]R-{a}/{a}细分[x]R-{a}的结论,证明了U/(R-{a})≠U/R与"U/R元素有兄弟"的等价性.然后基于二叉树设计思想,用兄弟存储结构设计了一个新的信息表求核算法,仅需生成较小的二叉树就能求核,时间复杂度和空间复杂度分别为O(|C|2|U|)和O(|U|).算法的主要贡献是将求核问题转化为等价类生成过程中兄弟的有无判断问题.通过实例验证了算法的有效性.     

Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

This paper presents an optimal sequential and an optimal parallel algorithm to compute a minimum cardinality Steiner set and a Steiner tree. The sequential algorithm takes O ( n ) time and parallel algorithm takes O (log n ) time and O ( n /log n ) processors on an EREW PRAM model.     

Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults

Tasks in hard real-time systems are required to meet preset deadlines, even in the presence of transient faults, and hence the analysis of worst-case finish time (WCFT) must consider the extra time incurred by re-executing tasks that were faulty. Existing solutions can only estimate WCFT and usually result in significant under- or over-estimation. In this work, we conclude that a sufficient and necessary condition of a task set experiencing its WCFT is that its critical task incurs all expected transient faults. A method is presented to identify the critical task and WCFT in O(|V | + |E|) where |V | and |E| are the number of tasks and dependencies between tasks, respectively. This method finds its application in testing the feasibility of directed acyclic graph (DAG) based task sets scheduled in a wide variety of fault-prone multi-processor systems, where the processors could be either homogeneous or heterogeneous, DVS-capable or DVS-incapable, etc. The common practices, which require the same time complexity as the proposed critical-task method, could either underestimate the worst case by up to 25%, or overestimate by 13%. Based on the proposed critical-task method, a simulated-annealing scheduling algorithm is developed to find the energy efficient fault-tolerant schedule for a given DAG task set. Experimental results show that the proposed critical-task method wins over a common practice by up to 40% in terms of energy saving.     

An efficient Dijkstra-like labeling method for computing shortest odd/even paths

We show how the problem of determining shortest paths of even or odd length between two specified vertices in a graph G = (V, E) can be reduced to the problem of finding a shortest alternating path with respect to a specific matching in a related graph H. This problem can be solved by a Dijkstra-like labeling procedure of complexity O(|V|²) respectively O(|E|log|V|). Interpreting this procedure appropriately the method can then be applied directly on the given graph G.     

Dynamic Programming on the Word RAM

Dynamic programming is one of the fundamental techniques for solving optimization problems. In this paper we propose a general framework which can be used to decrease the time and space complexity of these algorithms with a logarithmic factor. The framework is based on word encoding, i.e. by representing subsolutions as bits in an integer. In this way word parallelism can be used in the evaluation of the dynamic programming recursion. Using this encoding the subset-sum problem can be solved in O( n b/ log b) time and O(b/ log b) space, where n is the number of integers given and b is the target sum. The knapsack problem can be solved in O( n m/ log m) time and O(m/ log m) space, where n is the number of items and m = max{b,z} is the maximum of the capacity b and the optimal solution value z . The problem of finding a path of a given length b in a directed acyclic graph G=(V,E) can be solved in O(|E|b/ log b) time and O(|V|b/ log b) space. Several other examples are given showing the generality of the achieved technique. Extensive computational experiments are provided to demonstrate that the achieved results are not only of theoretical interest but actually lead to algorithms which are up to two orders of magnitude faster than their predecessors. This is a surprising observation as the increase in speed is larger than the word size of the processor.     

Constant Time Boolean Matrix Multiplication on a Linear Array with a Reconfigurable Pipelined Bus System

We show that the product of two N × N boolean matrices can be calculated in constant time on an LARPBS with O(N3 / log N) processors. All data communications and computations are performed on the bit level. To the best of the author's knowledge, this is the first parallel boolean matrix multiplication algorithm that has constant execution time, and is executed on a distributed memory system with (N3) processors. By using our boolean matrix multiplication algorithm, it is shown that the transitive closure of a directed graph can be obtained in O(log N) time ( measured by bit level operations) on an LARPBS with O (N3 / log N) processors. To the best of our knowledge, this is the first parallel algorithm for tansitive closure of directed graphs with time complexity O(log N) (comparable to that of CRCW PRAM) and cost O (N3) on a realistic parallel computing model, which has no shared memory, and interprocessor communications are dealt with explicitly and efficiently.     

Efficient geometric algorithms on the EREW PRAM

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM     

一种新的信息熵属性约简算法

给出一个区分对象对的属性约简定义,同时证明该属性约简的定义与基于信息熵的属性约简的定义是等价的。为求出区分对象对集,首先给出了一个快速求简化决策表的算法,其时间复杂度为O（|C||U|）。然后在简化决策表的基础上,设计了基于区分对象对集的信息熵属性约简算法,其时间复杂度和空间复杂度分别为O（|C||U|）+O（|C||U/C|²）和O（|U/C|²）+O（|U|）,最后用一个实例说明了新算法的高效性。     

基于数据库的属性约简模型的快速求核算法

对于基于数据库系统的属性约简模型,给出相应的简化差别矩阵和相应核的定义,并证明该核与基于数据库系统的属性约简模型的核是等价的。在此基础上设计了一个新的求核算法,其时间复杂度和空间复杂度分别为max{O（|C||U/C|²）,O（|C||U|）}和O（|U|）。