A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Efficient parallel algorithms for shortest paths in planar digraphs

Efficient parallel algorithms are presented, on the CREW PRAM model, for generating a succinct encoding of all pairs shortest path information in a directed planar graphG with real-valued edge costs but no negative cycles. We assume that a planar embedding ofG is given, together with a set ofq faces that cover all the vertices. Then our algorithm runs inO(log² n) time and employsO(nq+M(q)) processors (whereM(t) is the number of processors required to multiply twot×t matrices inO(logt) time). Let us note here that wheneverq<n then our processor bound is better than the best previous one (M(n)).O(log² n) time,n-processor algorithms are presented for various subproblems, including that of generating all pairs shortest path information in a directedouterplanar graph. Our work is based on the fundamental hammock-decomposition technique of G. Frederickson. We achieve this decomposition inO(logn log*n) parallel time by usingO(n) processors. The hammock-decomposition seems to be a fundamental operation that may help in improving efficiency of many parallel (and sequential) graph algorithms.This work was partially supported by the EEC ESPRIT Basic Research Action No. 3075 (ALCOM) and by the Ministry of Industry, Energy and Technology of Greece.     

An improved algorithm for the rectangle enclosure problem

Given a set of n rectangles in the plane, with sides parallel to the coordinate axes, the rectangle enclosure problem consists of finding all q pairs of rectangles such that one rectangle of the pair encloses the other. In this note we present an alternative algorithm to the one by Vaishnavi and Wood; while both techniques have worst-case running time O(nlog²n + q), ours uses optimal storage O(n) rather than O(nlog²n) of Vaishnavi and Wood. Our algorithm works entirely in-place and uses very conventional data structures.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

Vertical decompositions for triangles in 3-space

We prove that, for any constant ɛ>0, the complexity of the vertical decomposition of a set ofn triangles in three-dimensional space isO(n ^2+ɛ +K), whereK is the complexity of the arrangement of the triangles. For a single cell the complexity of the vertical decomposition is shown to beO(n ^2+ɛ ). These bounds are almost tight in the worst case. We also give a deterministic output-sensitive algorithm for computing the vertical decomposition that runs inO(n ² logn+V logn) time, whereV is the complexity of the decomposition. The algorithm is reasonably simple (in particular, it tries to perform as much of the computation in two-dimensional spaces as possible) and thus is a good candidate for efficient implementations. The algorithm is extended to compute the vertical decomposition of arrangements ofn algebraic surface patches of constant maximum degree in three-dimensional space in timeO(nλ _q (n) logn +V logn), whereV is the combinatorial complexity of the vertical decomposition, λ _q (n) is a near-linear function related to Davenport-Schinzel sequences, andq is a constant that depends on the degree of the surface patches and their boundaries. We also present an algorithm with improved running time for the case of triangles which is, however, more complicated than the first algorithm. Mark de Berg was supported by the Dutch Organization for Scientific Research (N.W.O.), and by ESPRIT Basic Research Action No. 7141 (project ALCOM II:Algorithms and Complexity). Leonidas Guibas was supported by NSF Grant CCR-9215219, by a grant from the Stanford SIMA Consortium, by NSF/ARPA Grant IRI-9306544, and by grants from the Digital Equipment, Mitsubishi, and Toshiba Corporations. Dan Halperin was supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. A preliminary version of this paper appeared inProc. 10th ACM Symposium on Computational Geometry, 1994, pp. 1–10.     

Embeddings of Un(q2) and symmetric strongly regular graphs

In the geometric setting of the embedding of the unitary group U_n(q²) inside an orthogonal or a symplectic group over the subfield GF(q) of GF(q²), q odd, we show the existence of infinite families of transitive two‐character sets with respect to hyperplanes that in turn define new symmetric strongly regular graphs and two‐weight codes. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 248–253, 2010     

A Parallel Reduction of Hamiltonian Cycle to Hamiltonian Path in Tournaments

We propose a parallel algorithm which reduces the problem of computing Hamiltonian cycles in tournaments to the problem of computing Hamiltonian paths. The running time of our algorithm is O(log n) using O(n²/log n) processors on a CRCW PRAM, and O(log n log log n) on an EREW PRAM using O(n²/log n log log n) processors. As a corollary, we obtain a new parallel algorithm for computing Hamiltonian cycles in tournaments. This algorithm can be implemented in time O(log n) using O(n²/log n) processors in the CRCW model and in time O(log²n) with O(n²/log n log log n) processors in the EREW model.     

A fast and simple randomized parallel algorithm for the maximal independent set problem

A simple parallel randomized algorithm to find a maximal independent set in a graph G = (V, E) on n vertices is presented. Its expected running time on a concurrent-read concurrent-write PRAM with O(|E|d_max) processors is O(log n), where d_max denotes the maximum degree. On an exclusive-read exclusive-write PRAM with O(|E|) processors the algorithm runs in O(log²n). Previously, an O(log⁴n) deterministic algorithm was given by Karp and Wigderson for the EREW-PRAM model. This was recently (independently of our work) improved to O(log²n) by M. Luby. In both cases randomized algorithms depending on pairwise independent choices were turned into deterministic algorithms. We comment on how randomized combinatorial algorithms whose analysis only depends on d-wise rather than fully independent random choices (for some constant d) can be converted into deterministic algorithms. We apply a technique due to A. Joffe (1974) and obtain deterministic construction in fast parallel time of various combinatorial objects whose existence follows from probabilistic arguments.     

A sublogarithmic convex hull algorithm

We present a parallel algorithm for finding the convex hull of a sorted set of points in the plane. Our algorithm runs inO(logn/log logn) time usingO(n log logn/logn) processors in theCommon crcw pram computational model, which is shown to be time and cost optimal. The algorithm is based onn ^1/3 divide-and-conquer and uses a simple pointer-based data structure.Part of this work was done when the last three authors were at the Department of Computer and Information Science, Linköping University. The research of the second author was supported by the Academy of Finland.     

Reed-Muller codes and Barnes-Wall lattices: Generalized multilevel constructions and representation over GF(2<Superscript><Emphasis Type="Italic">q</Emphasis></Superscript>)

Generalized multilevel constructions for binary RM(r,m) codes using projections onto GF(2 ^q ) are presented. These constructions exploit component codes over GF(2), GF(4),..., GF(2 ^q ) that are based on shorter Reed-Muller codes and set partitioning using partition chains of length-2 ^l codes. Using these constructions we derive multilevel constructions for the Barnes-Wall Λ(r,m) family of lattices which also use component codes over GF(2), GF(4),..., GF(2 ^q ) and set partitioning based on partition chains of length-2 ^l lattices. These constructions of Reed-Muller codes and Barnes-Wall lattices are readily applicable for their efficient decoding.      

Fast rectangular matrix multiplication and some applications

We study asymptotically fast multiplication algorithms for matrix pairs of arbitrary di- mensions, and optimize the exponents of their arithmetic complexity bounds. For a large class of input matrix pairs, we improve the known exponents. We also show some applications of our results:(i) we decrease from O(n~2 n~(1 o)(1)logq)to O(n~(1.9998) n~(1 o(1))logq)the known arithmetic complexity bound for the univariate polynomial factorization of degree n over a finite field with q elements; (ii) we decrease from 2.837 to 2.7945 the known exponent of the work and arithmetic processor bounds for fast deterministic(NC)parallel evaluation of the determinant, the characteristic polynomial, and the inverse of an n×n matrix, as well as for the solution to a nonsingular linear system of n equations; (iii)we decrease from O(m~(1.575)n)to O(m~(1.5356)n)the known bound for computing basic solutions to a linear programming problem with m constraints and n variables.     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

Optimal parallel quicksort on EREW PRAM

In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.     

Fast broadcasting and gossiping in radio networks

We establish an O(nlog²n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n^3/2). Using our broadcasting algorithm, we develop an O(n^3/2log²n) algorithm for gossiping in the same network model.     

On the k-error linear complexity of sequences with period 2pn over GF(q)

In this paper, we first optimize the structure of the Wei–Xiao–Chen algorithm for the linear complexity of sequences over GF(q) with period N =  2p ⁿ , where p and q are odd primes, and q is a primitive root modulo p ². The second, an union cost is proposed, so that an efficient algorithm for computing the k-error linear complexity of a sequence with period 2p ⁿ over GF(q) is derived, where p and q are odd primes, and q is a primitive root modulo p ². The third, we give a validity of the proposed algorithm, and also prove that there exists an error sequence e ^N , where the Hamming weight of e ^N is not greater than k, such that the linear complexity of (s + e) ^N reaches the k-error linear complexity c. We also present a numerical example to illustrate the algorithm. Finally, we present the minimum value k for which the k-error linear complexity is strictly less than the linear complexity.     

An efficient pram algorithm for maximum-weight independent set on permutation graphs

An efficient parallel algorithm is presented to find a maximum weight independent set of a permutation graph which takesO (logn) time usingO (n ²/logn) processors on an EREW PRAM, provided the graph has at mostO (n) maximal independent sets. The best known parallel algorithm takesO (log² n) time andO (n ³/logn) processors on a CREW PRAM.     

Diameters of finite upper half plane graphs

Let GF(q) be a finite field of q elements. Let G denote the group of matrices M(x, y) = (^{y x}_{0 1}) over GF(q) with y ≠ 0. Fix an irreducible polynomial For each a ϵ GF(q), let X_a be the graph whose vertices are the q² − q elements of G, with two vertices M(x, y), M(v, w) joined by an edge if and only if The graphs X_a with a ϵ/ {0, t² − 4n} are (q + 1)-regular connected graphs which have received recent attention, as they've been shown to be Ramanujan graphs. We determine the diameter of these graphs X_a. © 1996 John Wiley & Sons, Inc.     

Efficient Computation of Rectilinear Geodesic Voronoi Neighbor in the Presence of Obstacles

In this paper we present an algorithm to compute the rectilinear geodesic voronoi neighbor of an arbitrary query pointqamong a setSofmpoints in the presence of a set ofnvertical line segment obstacles inside a rectangular floor. The distance between a pair of points α and β is the shortest rectilinear distance avoiding the obstacles in and is denoted by δ(α, β). The rectilinear geodesic voronoi neighbor of an arbitrary query pointq,RGVN(q) is the pointp_i ∈ Ssuch that δ(q, p_i) is minimum. The algorithm suggests a preprocessing of the elements of the setsSand inO((m + n)log(m + n)) time such that for an arbitrary query pointq, theRGVNquery can be answered inO(log(m + n)) time. The space required for storing the preprocessed information isO(n + m log m). If the points inSare placed on the boundary of the rectangular floor, a different technique is adopted to decrease the space complexity toO(m + n). This technique works even if the obstacles are rectangles instead of line segments. Finally, the parallelization of the preprocessing steps for the latter algorithm is suggested, which takesO(log³(m + n)) time, usingO((m + n)^1.5/log²(m + n)) processors andO(log(m + n)) query time.