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.     

Optimal Sequential and Parallel Algorithms to Compute All Cut Vertices on Trapezoid Graphs

In this paper, a sequential algorithm is presented to find all cut-vertices on trapezoid graphs. To every trapezoid graph G there is a corresponding trapezoid representation. If all the 4n corner points of n trapezoids, in a trapezoid representation of a trapezoid graph G with n vertices, are given, then the proposed sequential algorithm runs in O(n) time. Parallel implementation of this algorithm can be done in O(log n) time using O(n/ log n) processors on an EREW PRAM model.     

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.     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matching parentheses in parallel

Parallel algorithms for evaluating arithmetic expressions generally assume the computation tree form to be at hand. The computation tree form can be generated within the same resource bounds as the parenthesis matching problem can be solved. We provide a new cost optimal parallel algorithm for the latter problem, which runs in time O(log n) using O(n/log n) processors on an . We also prove that the algorithm is the fastest possible independently of the number of processors available.     

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.     

Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random k ‐coloring of an n ‐vertex graph with maximum degree Δ. We prove that, for every ε > 0, the dynamics converges to a random coloring within O(nlog n) steps assuming k ≥ k₀(ε) and either: (i) k/Δ > α* + ε where α*≈? 1.763 and the girth g ≥ 5, or (ii) k/Δ >β * + ε where β*≈? 1.489 and the girth g ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on k/Δ and the minimum girth but also required Δ = Ω (log n). The best known result for general graphs is O(nlog n) mixing time when k/Δ > 2 and O(n²) mixing time when k/Δ > 11/6. Related results of Goldberg et al apply when k/Δ > α* for all Δ ≥ 3 on triangle‐free “neighborhood‐amenable” graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

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.     

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.     

Linear sorting withO(logn) processors

A file ofn records can be sorted in linear time givenO(log(n)) processors. Four such algorithms are presented and analyzed. All of them have reasonable hardware requirements; no memory access conflicts are generated; a constant number of communication lines per processor are needed (except for one case); and the space requirements areO(n) orO(n log(log(n))).     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.     

Parallel algorithms for analyzing activity networks

Parallel algorithms for analyzing activity networks are proposed which include feasibility test, topological ordering of the events, and computing the earliest and latest start times for all activities and hence identification of the critical activities of the activity network. The first two algorithms haveO(logn) time complexity and the remaining one achievesO(logd log logn) time bound, whered is the diameter of the digraph representing the activity network withn nodes. All these algorithms work on a CRCW PRAM and requireO(n ³) processors.     

Greedy colorings of uniform hypergraphs

We give a very short proof of an Erd?s conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2ⁿ, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn^1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn^1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

An NC Parallel Algorithm for Edge-Coloring Series–Parallel Multigraphs

Many combinatorial problems can be efficiently solved in parallel for series–parallel multigraphs. The edge-coloring problem is one of a few combinatorial problems for which no NC parallel algorithm has been obtained for series–parallel multigraphs. This paper gives an NC parallel algorithm for the problem on series–parallel multigraphsG. It takesO(log n) time withO(Δn/log n) processors, wherenis the number of vertices and Δ is the maximum degree ofG.     

An Efficient Algorithm for a Sparse k-Edge-Connectivity Certificate

We present an efficient algorithm for finding a sparse k-edge-connectivity certificate of a multigraph G. Our algorithm runs in O((log kn)(log k)²(log n)²) time using O(k(n + m′)) processors on an ARBITRARY CRCW PRAM, where n and m′ stand for the numbers of vertices in G and edges in the simplified graph of G, respectively.     

The average performance of a parallel stable marriage algorithm

In this paper, Tseng and Lee's parallel algorithm to solve the stable marriage prolem is analyzed. It is shown that the average number of parallel proposals of the algorithm is of ordern by usingn processors on a CREW PRAM, where each parallel proposal requiresO(loglog(n) time on CREW PRAM by applying the parallel selection algorithms of Valiant or Shiloach and Vishkin. Therefore, our parallel algorithm requiresO(nloglog(n)) time. The speed-up achieved is log(n)/loglog(n) since the average number of proposals required by applying McVitie and Wilson's algorithm to solve the stable marriage problem isO(nlog(n)).     

Triply-Logarithmic Parallel Upper and Lower Bounds for Minimum and Range Minima over Small Domains

We consider the problem of computing the minimum ofnvalues, and several well-known generalizations [prefix minima, range minima, and all nearest smaller values (ANSV)] for input elements drawn from the integer domain [1···s], wheres ≥ n. In this article we give simple and efficient algorithms for all of the preceding problems. These algorithms all takeO(log log log s) time using an optimal number of processors andO(ns^ε) space (for constant ε < 1) on the COMMON CRCW PRAM. The best known upper bounds for the range minima and ANSV problems were previouslyO(log log n) (using algorithms for unbounded domains). For the prefix minima and for the minimum problems, the improvement is with regard to the model of computation. We also prove a lower bound of Ω(log log n) for domain sizes = 2^{Ω(log n log log n)}. Since, forsat the lower end of this range, log log n = Ω(log log log s), this demonstrates that any algorithm running ino(log log log s) time must restrict the range ofson which it works.     

Polygon triangulation inO(n log logn) time with simple data structures

We give a newO(n log logn)-time deterministic algorithm for triangulating simplen-vertex polygons, which avoids the use of complicated data structures. In addition, for polygons whose vertices have integer coordinates of polynomially bounded size, the algorithm can be modified to run inO(n log*n) time. The major new techniques employed are the efficient location of horizontal visibility edges that partition the interior of the polygon into regions of approximately equal size, and a linear-time algorithm for obtaining the horizontal visibility partition of a subchain of a polygonal chain, from the horizontal visibility partition of the entire chain. The latter technique has other interesting applications, including a linear-time algorithm to convert a Steiner triangulation of a polygon into a true triangulation.This research was partially supported by the following grants: NSERC 583584, NSERC 580485, ONR-N00014-87-0467, and by DIMACS, an NSF Science and Technology Center (NSF-STC88-09648).     

Periods in missing lengths of rainbow cycles

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define Then ??(G) is a monoid with respect to the operation n°m=n+ m?2, and thus there is a least positive integer π(G), the period of ??(G), such that ??(G) contains the arithmetic progression {N+ kπ(G)|k?0} for some sufficiently large N. Given that n∈??(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n?3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈??(G) then π(G) is a divisor of p(n). Moreover, ??(G) contains the arithmetic progression {N+ kp(n)|k?0} for some N=O(n²). The key observations are: If 2<n=2k∈??(G) then 3n?8∈??(G). If 16≠n=4k∈??(G) then 3n?10∈??(G). The main result cannot be improved since for every k>0 there are G, H such that 4k∈??(G), π(G)=2, and 4k+ 2∈??(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory     

On the characterization of p ‐adic Colombeau–Egorov generalized functions by their point values

We show that contrary to recent papers by S. Albeverio, A. Yu. Khrennikov and V. Shelkovich, point values do not determine elements of the so‐called p ‐adic Colombeau–Egorov algebra ??(?ⁿ _p ) uniquely. We further show in a more general way that for an Egorov algebra ??(M, R) of generalized functions on a locally compact ultrametric space (M, d) taking values in a nontrivial ring, a point value characterization holds if and only if (M, d) is discrete. Finally, following an idea due to M. Kunzinger and M. Oberguggenberger, a generalized point value characterization of ??(M, R) is given. Elements of ??(?ⁿ _p ) are constructed which differ from the p ‐adic δ ‐distribution considered as an element of ??(?ⁿ _p ), yet coincide on point values with the latter. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)