Abstract Given a plane graph $G=(V,E)$ , a Petrie tour of G is a tour P of G that alternately turns left and right at each step. A Petrie tour partition of G is a collection ${\mathscr P}=\{P_1,\ldots,P_q\}$ of Petrie tours so that each edge of G is in exactly one tour $P_i \in {\mathscr P}$ . A Petrie tour P is called a Petrie cycle if all its vertices are distinct. A Petrie cycle partition of G is a collection ${\mathscr C}=\{C_1,\ldots,C_p\}$ of Petrie cycles so that each vertex of G is in exactly one cycle $C_i \in {\mathscr C}$ . In this paper, we study the properties of 3-regular plane graphs that have Petrie cycle partitions and 4-regular plane multi-graphs that have Petrie tour partitions. Given a 4-regular plane multi-graph $G=(V,E)$ , a 3-regularization of G is a 3-regular plane graph $G_3$ obtained from G by splitting every vertex $v\in V$ into two degree-3 vertices. G is called Petrie partitionable if it has a 3-regularization that has a Petrie cycle partition. The general version of this problem is motivated by a data compression method, tristrip, used in computer graphics. In this paper, we present a simple characterization of Petrie partitionable graphs and show that the problem of determining if G is Petrie partitionable is NP-complete.

We present an optimal parallel selection algorithm on the EREW PRAM. This algorithm runs in O (log n ) time with n /log n processors. This complexity matches the known lower bound for parallel selection on the EREW PRAM model. We therefore close this problem which has been open for more than a decade.

To study the resequencing delay caused by multipath routing, we consider a system of parallel queues under random routing as a model of network routing behavior. The impact of resequencing on packet end-to-end delay is explored through the newly introduced resequencing index. We compute this new metric under several distributional asumptions (e.g., light vs. heavy tails) on routing delays.

Proxy Web caching is commonly implemented to decrease Web access latency, Internet bandwidth costs and origin Web server load. We propose a transparent shareable proxy caching methodology in which the proxy caches maintain a continuously optimal performance with a significant improvement in the cache hit ratio without requiring any additional overhead at the client or at the routers. This approach allows caches' to be personalized based on the users' Web access patterns. Our approach employs four light weight intelligent agents in a system of proxy caches which use classification algorithms, data mining techniques and performance monitors to study the client's Web access patterns and configure caches to best serve the clients with available resources. These agents run with predictable run times with an optimal use of computer resources.

We present a randomized algorithm sorting n integers in O(n/spl radic/(log log n)) expected time and linear space. This improves the previous O(n log log n) bound by Anderson et al. (1995). As an immediate consequence, if the integers are bounded by U, we can sort them in O(n/spl radic/(log log U)) expected time. This is the first improvement over the O (n log log U) bound obtained with van Emde Boas' data structure. At the heart of our construction, is a technical deterministic lemma of independent interest; namely, that we split n integers into subsets of size at most /spl radic/n in linear time and space. This also implies improved bounds for deterministic string sorting and integer sorting without multiplication.

We present a fast deterministic algorithm for integer sorting in linear space. Our algorithm sorts n integers in the range {0, 1, 2, …, m—1} in linear space in O(n log log n) time. This improves our previous result [8] which sorts in O(n log log n log log log n) time and linear space. This also improves previous best deterministic sorting algorithm [3, 11] which sorts in O(nlog log n) time but uses O(me) space. Our results can also be compared with Thorup's previous result [16] which sorts in O(nlog log n) time and linear space but uses randomization.

We present a significant improvement for parallel integer sorting. On the EREW (exclusive read exclusive write) PRAM our algorithm sorts n integers in the range {0,1, . . . ,m-1 } in time O(log n) with $O(n \sqrt{\frac{\log n}{k}})$ operations using word length $k \log (m+n)$, where $1 \leq k \leq \log n$. In this paper we present the following four variants of our algorithm. \noindent (1) The first variant sorts integers in $\{ 0, 1, \ldots, m-1\}$ in time O(log n) and in linear space with O(n) operations using word length log m log n. (2) The second variant sorts integers in {0, 1, . . , n-1} in time O(log n) and in linear space with $O(n\sqrt{\log n})$ operations using word length log n. (3) The third variant sorts integers in {0, 1, . . . , m-1} in time O(log 3/2 n ) and in linear space with $O(n\sqrt{\log n})$ operations using word length log (m+n). (4) The fourth variant sorts integers in {0, 1, . . . ,m-1} in time O(log n) and space $O(nm^\epsilon )$ with $O(n\sqrt{\log n})$ operations using word length log (m+n). Our algorithms can then be generalized to the situation where the word length is k log (m+n), $1 \leq k \leq \log n$.

The linear array with a reconfigurable pipelined bus system (LARPBS) is a newly introduced parallel computational model, where processors are connected by a reconfigurable optical bus. In this paper, we show that the selection problem can be solved on the LARPBS model deterministically in O((loglogN)/sup 2// log log log N) time. To our best knowledge, this is the best deterministic selection algorithm on any model with a reconfigurable optical bus.

Dynamic and complex computation in the area of Geographic Information System (GIS) or Mobile Computing System involves huge amount of spatial objects such as points, boxes, polygons, etc and requires a scalable data structure and an efficient management tool for this information. In this paper, for a dynamic management of spatial objects, we construct a hierarchical dynamic data structure, called an IST/OPG hierarchy, which may overcome some limitations of existing Spatial Access Methods (SAMs). The hierarchy is constructed by combining three primary components: (1) Minimum Boundary Rectangle (MBR), which is the most widely used method among SAMs; (2) the population-based domain slicing, which is modified from the Grid File [14]; (3) extended optimal Integer Searching algorithm [4]. For dynamic management of spatial objects in the IST/OPG hierarchy, a number of primary and supplementary operations are introduced. This paper includes a comparative analysis of our approach with previous SAMs, such as R-Tree, R+-Tree and R*-Tree and QSF-Tree. The results of analysis show that our approach is better than other SAMs in construction and query time and space requirements. Specifically, for a given search domain with n objects, our query operations yield $O($ \scriptsize $\sqrt {\frac {\log n} {\log\log n}}$\normalsize $)$ compared to $O(\log n)$ of the fast SAM and an IST/OPG hierarchy containing $n$ objects can be constructed in $O(n$ \scriptsize $\sqrt {\frac {\log n}{\log\log n}}$\normalsize $)$ time and O(n) space.

This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O (log n ) time. Specifically, we present a new algorithm to solve these problems in O (log n ) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the “OR” of n bit requires Ω(log n time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.

This paper presents a fast derandomization scheme for the PROFIT/COST problem. Through the applications of this scheme the time complexity of $O(\log ^2 n\log \log n)$ for the $\Delta + 1$ vertex-coloring problem using $O({{(m + n)} / {\log \log n}})$ processors on the concurrent read exclusive write parallel random-access machine (CREW PRAM), the time complexity of $O(\log ^{2.5} n)$ for the maximal independent set problem using $O({{(m + n)} / {\log ^{1.5} n}})$ processors on the CREW PRAM and the time complexity of $O(\log ^{2.5} n)$ for the maximal matching problem using $O({{(m + n)} / {\log ^{0.5} n}})$ processors on the exclusive read exclusive write (EREW) PRAM are shown.

We present efficient parallel shortest path algorithms for an n x n banded matrix of bandwidth b. Our algorithm computes all pair shortest distances within the band in time O(nb^{2}/p + l(b)logblog(n/b)) on the PRAM using p processors, where l(b) is logb on the EREW PRAM, loglogb on the CRCW PRAM, and a constant on the randomized CRCW PRAM. It computes all pair shortest distances in time O(n^{2}b/p+l(B)logblog(n/b)) using p processors.

recursive steps in the worst case and thus require at least the order of n time in their parallel im-We present parallel algorithms for computing all plementation, even if the number of available propair shortest paths in directed graphs.Our algocessors is not bounded.O(n) time and n2 procesrithm has time complexity O(j(n)/p + l(n) log n) sor bounds can indeed be achieved, for inst ante, on the PRAM using p processors, where I(n) is in the straightforward parallelization of the algolog non the EREW PRAM, log log n on the CRCW rithm of [Fl].(Here and hereafter we assume the PRAM, ~(n) is o(n3).On the randomized CRCW customary PRAM models of parallel computing PRAM we are able to achieve time complexity [KR].)0(n3/p + iog n) using p processors.NC algorithms are also available for this problem.However, they either need O(n3 log n) ope-

The author presents a deterministic parallel algorithm for the linked list prefix problem. It computes linked list prefixs for an input list of n elements in time O(n/p+logn) on a local memory PRAM model using p processors and p shared memory cells.>

We present an algorithm for determining the shortest path between a source point and any destination point along the surface of a polyhedron (need not be convex). Our algorithm uses a new approach which deviates from the conventional “continuous Dijkstra” technique. It takes Ο(n2) time and ⊖(n) space to determine the shortest path and to compute the inward layout which can be used to construct a structure for processing queries of shortest path from the source point to any destination point.

A parallel algorithm for computing the connected components of undirected graphs is presented. Shared memory computation models are assumed. For a graph of e edges and n nodes, the time complexity of the algorithm is Ο( e/p + ( n log n )/ p + log 2 n ) with p processors. The algorithm can be further refined to yield time complexity Ο( H ( e , n , p )/ p + ( n log n )/( p log( n / p )) + log 2 n ), where H ( e, n, p ) is very close to Ο( e ). These results show that linear speedup can be obtained for up to p ≤ e /log 2 n processors when e ≥ n log n . Linear speedup can still be achieved with up to p ≤ n ε processors, 0 ≤ ε < 1, for graphs satisfying e ≥ n log (*) n . Our results can be further improved if a more efficient integer sorting algorithm is available.

Article Free Access Share on Matching partition a linked list and its optimization Author: Y. Han Department of Computer Science, University of Kentucky, Lexington, KY Department of Computer Science, University of Kentucky, Lexington, KYView Profile Authors Info & Claims SPAA '89: Proceedings of the first annual ACM symposium on Parallel algorithms and architecturesMarch 1989 Pages 246–253https://doi.org/10.1145/72935.72961Published:01 March 1989Publication History 9citation373DownloadsMetricsTotal Citations9Total Downloads373Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF