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

Representing shared data on distributed-memory parallel computers

The problem of representing a setU≜{u ₁,...,u _m} of read-write variables on ann-node distributed-memory parallel computer is considered. It is shown thatU can be represented among then nodes of a variant of the mesh of trees usingO((m/n) polylog(m/n)) storage per node such that anyn-tuple of variables may be accessed inO(logn (log logn)²) time in the worst case form polynomial inn. This work was supported in part by the Joint Services Electronics Program under Contract F49620-87-C-0044 and by IBM under Agreement 12060043. Earlier versions of these results appeared in theProceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, October 1989 and in theProceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, Crete, July 1990.     

Selection, Routing, and Sorting on the Star Graph

We consider the problems of selection, routing, and sorting on ann-star graph (withn! nodes), an interconnection network which has been proven to possess many special properties. We identify a tree like subgraph (which we call a “(k, 1,k) chain network”) of the star graph which enables us to design efficient algorithms for the above mentioned problems. We present an algorithm that performs a sequence ofnprefix computations inO(n²) time. This algorithm is used as a subroutine in our other algorithms. We also show that sorting can be performed on then-star graph in timeO(n³) and that selection of a set of uniformly distributednkeys can be performed inO(n²) time with high probability. Finally, we also present a deterministic (nonoblivious) routing algorithm that realizes any permutation inO(n³) steps on then-star graph. There exists an algorithm in the literature that can perform a single prefix computation inO(nlgn) time. The best-known previous algorithm for sorting has a run time ofO(n³lgn) and is deterministic. To our knowledge, the problem of selection has not been considered before on the star graph.     

Faster communication in known topology radio networks

This paper concerns the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed in advance based on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient algorithm for computing a radio schedule of length D + O(log³ n), and a randomized algorithm for computing a radio schedule of length D + O(log² n). These results improve on the best currently known D + O(log⁴ n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log³ n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time , for any network with the diameter D = Ω(log ⁱ⁺⁴ n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log³ n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231, 2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms 52(1), 8–25, 2004). The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering. Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool.     

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.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.     

An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.     

Maximum matchings in planar graphs via gaussian elimination

We present a randomized algorithm for finding maximum matchings in planar graphs in timeO(n ^ω/2), whereω is the exponent of the best known matrix multiplication algorithm. Sinceω<2.38, this algorithm breaks through theO(n ^1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs. We also present an algorithm for generating perfect matchings in planar graphs uniformly at random usingO(n ^ω/2) arithmetic operations. Our algorithms are based on the Gaussian elimination approach to maximum matchings introduced in [16]. This research was supported by KBN Grant 4T11C04425.     

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.     

A faster parallel algorithm for a matrix searching problem

We give an improved parallel algorithm for the problem of computing the tube minima of a totally monotonen ×n ×n matrix, an important matrix searching problem that was formalized by Aggarwal and Park and has many applications. Our algorithm runs inO(log logn) time withO(n²/log logn) processors in theCRCW-PRAM model, whereas the previous best ran inO((log logn)²) time withO(n²/(log logn)² processors, also in theCRCW-PRAM model. Thus we improve the speed without any deterioration in thetime ×processors product. Our improved bound immediately translates into improvedCRCW-PRAM bounds for the numerous applications of this problem, including string editing, construction of Huffmann codes and other coding trees, and many other combinatorial and geometric problems.This research was supported by the Office of Naval Research under Grants N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Part of the research was done while the author was at Princeton University, visiting the DIMACS center.     

Improved edge-coloring with three colors

We show an O(1.344ⁿ)=O(2^0.427n) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous O(2^n/2) algorithm of Beigel and Eppstein [R. Beigel, D. Eppstein, 3-coloring in time O(1.3289n), J. Algorithms 54 (2) (2005) 168–204.]. We apply a very natural approach of generating inclusion–maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

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.

     

A fast algorithm for computing sparse visibility graphs

AnO(¦E¦log² n) algorithm is presented to construct the visibility graph for a collection ofn nonintersecting line segments, where ¦E¦ is the number of edges in the visibility graph. This algorithm is much faster than theO(n ²)-time andO(n ²)-space algorithms by Asanoet al., and by Welzl, on sparse visibility graphs. Thus we partially resolve an open problem raised by Welzl. Further, our algorithm uses onlyO(n) working storage.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.     

Virtual Shared Memory: Algorithms and Complexity

We consider the Block PRAM model of Aggarwal et al. (in "Proceedings, First Annual ACM Symposium on Parallel Algorithms and Architectures, 1989," pp. 11-21). For a Block PRAM model with n/log n processors and communication latency l = O(log n), we show that prefix sums can be performed in time O(l log n/log l), but list ranking requires time Ω(l log n); these bounds are tight. These results justify an intuitive observation of Gazit et al. (in "Proceedings, 1987 Princeton Workshop on Algorithm, Architecture and Technology Issues for Models of Concurrent Computation," pp. 139-156) that algorithm designers should, when possible, replace the list ranking procedure with the prefix sums procedure. We demonstrate the value of this technique in choosing between two optimal PRAM algorithms for finding the connected components of dense graphs. We also give theoretical improvements for integer sorting and many other algorithms based on prefix sums, and suggest a relationship between the issue of graph density for the connected components problem and alternative approaches to integer sorting.     

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.     

Visibility of disjoint polygons

Consider a collection of disjoint polygons in the plane containing a total ofn edges. We show how to build, inO(n ²) time and space, a data structure from which inO(n) time we can compute the visibility polygon of a given point with respect to the polygon collection. As an application of this structure, the visibility graph of the given polygons can be constructed inO(n ²) time and space. This implies that the shortest path that connects two points in the plane and avoids the polygons in our collection can be computed inO(n ²) time, improving earlierO(n ² logn) results.     

Maintaining dynamic sequences under equality tests in polylogarithmic time

We present a randomized and a deterministic data structure for maintaining a dynamic family of sequences under equality tests of pairs of sequences and creations of new sequences by joining or splitting existing sequences. Both data structures support equality tests inO(1) time. The randomized version supports new sequence creations inO(log² n) expected time wheren is the length of the sequence created. The deterministic solution supports sequence creations inO(logn(logmlog^* m+logn)) time for themth operation. This work was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (Project ALCOM II).     

RL \subseteq SC

We show that any randomized logspace algorithm (running in polynomial time with bounded two-sided error) can be simulated deterministically in polynomial time andO(log² n) space. This puts RL in SC, Steve's Class In particular, we get a polynomial time,O(log² n) space algorithm for thest-connectivity problem on undirected graphs.Subject classifications. 68Q10, 68Q15, 68Q25.     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.