The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We describe a methodology for constructing parallel algorithms that are transportable among parallel computers having different numbers of processors, different bandwidths of interprocessor communication and different periodicity of global synchronisation. We do this for the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of a parallel machine into three numerical parameters...
The traditional model of learning in the limit is restricted so as to allow the learning machines only a fixed, finite amount of memory to store input and other data. A class of recursive functions is presented that cannot be learned deterministically by any such machine, but can be learned by a memory limited probabilistic leaning machine with probability 1.
The k-compaction problem arises when k out of n cells in an array are non-empty and the contents of these cells must be moved to the first k locations in the array. Parallel algorithms for k-compaction have obvious applications in processor allocation and load balancing; k-compaction is also an important subroutine in many recently developed parallel algorithms. We show that any EREW PRAM that solves...
In this talk we will consider various classes defined by small depth polynomial size circuits which contain threshold gates and parity gates. We will describe various inclusions between many classes defined in this way and also classes whose definitions rely upon spectral properties of Boolean functions.
Fredman and Knuth have treated certain recurrences, such as M(0)=1 and $$M\left( {n + 1} \right) = \mathop {\min }\limits_{0 \leqslant k \leqslant n} \left( {\alpha M(k) + \beta M(n - k)} \right),$$ where min(α, β)>1. Their treatment depends on certain auxiliary recurrences, such as $$h\left( x \right) = \left\{ \begin{gathered}0,if0 \leqslant x < 1; \hfill \\1 + h\left( {{x \mathord{\left/{\vphantom...
This paper considers the computation of matrix chain products of the form M1xM2x... Mn−1. The order in which the matrices are multiplied affects the number of operations. The best sequential algorithm for computing an optimal order of matrix multiplication runs in O(n log n) time while the best known parallel NC algorithm runs in O(log2 ...
A k- spanner of a connected graph G=(V, E) is a subgraph G′ consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G′ is larger than that distance in G by no more than a factor of k. This note concerns the problem of finding the sparsest 2-spanner in a given graph, and presents an approximation algorithm for this problem...
We obtain the first deterministic NC algorithm for the lowdiameter graph decomposition problem on arbitrary graphs. We achieve this through derandomizing an algorithm of Linial and Saks. Our algorithm runs in O(log5(n)) time and uses O(n2) processors.
We present a parallel algorithm for recognizing cographs and constructing their cotrees. The algorithm takes O(log2n) time with O(n+m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of the graph. Using cotree representation, we obtain a parallel algorithm for the permutation representation problem for cographs using O(log n) time with O(n) processors. We also...
The link metric, defined on a constrained region R of the plane, sets the distance between a pair of points in R equal the minimum number of segments or links that are needed to construct a path in R between the points. The minimum link path problem is to compute a path consisting of minimum number of links between two points in R, when R is the inside of a simple polygon P of size ns. Recently Chandru...
We present new algorithms for k- k routing on mesh connected processor arrays with wrap-around connections. Using new techniques for the performance analysis we show that an original randomized four stage algorithm performs optimally: for all k≥8, k-permutations are routed on the torus with k · n/4 + O((k · n · log n)1/2) routing steps and queue size k + o(k) with very high probability. We prove comparable...
This paper presents parallel algorithms for priority queue operations on a p-processor EREW-PRAM. The algorithms are based on a new data structure, the Min-path Heap (MH), which is obtained as an extension of the traditional binary-heap organization. Using an MH, it is shown that insertion of a new item or deletion of the smallest item from a priority queue of n elements can be performed in O log...
I show how to put n values into heap order in O(log log n) time using n/ log log n processors in the parallel comparison tree model of computation, and in Õ(α(n)) time on n/α(n) processors, in the randomized parallel comparison tree model, where α(n) is an inverse of Ackerman's function. I prove similar bounds for the related problem of putting n values into a min-max heap.
In PODS'91, Nurmi and Soisalon-Soininen presented a new type of binary search tree for databases, which they call a chromatic tree. The aim is to improve runtime performance by allowing a greater degree of concurrency, which, in turn, is obtained by uncoupling updating from rebalancing. This also allows rebalancing to be postponed completely or partially until after peak working hours. The...
Scheduling problems with interprocessor communication delays have been shown to be NP-complete ([PY88],[C90],[CP91],[P91]). This paper considers the scheduling problem with the restriction that the underlying DAGs are trees and each task has unit execution time. It is shown that the problem remains NP-complete for binary trees and uniform communication delays. The same holds for complete binary trees,...
We consider the list update problem under a sequence of requests of sets of items, and for this problem we investigate the competitiveness features of two algorithms. We prove that algorithm Move-Set-to-Front (MSF) is (1+βs)-competitive, where β is the size of the largest requested set, and that a lower bound is roughly 2. We provide an upper bound to the MSF competitive ratio by relating it to the...
We introduce a new multi-dimensional data structure based on binary trees called gkd-tree that generalizes several previously defined data structures, including the widely accepted kd-trees. Up to the present, gkd-trees are the fastest on-line improvement over kd-trees due to the combined effects of storing more than one element per node and making local reorganizations during insertions. The improvement...
We give an alternate implementation of the fractional cascading data-structure of Chazelle and Guibas to do iterative search for a key in multiple ordered lists. The construction of our data-structure uses randomization and simplifies the algorithm of Chazelle and Guibas vastly making it practical to implement. Although our bounds are asymptotically similar to the earlier ones, there are improvements...
We study the problem of maintaining the 2-edge-, 2-vertex-, and 3-edge-connected components of a dynamic planar graph subject to edge deletions. The 2-edge-connected components can be maintained in a total of O(n log n) time under any sequence of at most O(n) deletions. This gives O(log n) amortized time per deletion. The 2-vertex- and 3-edge-connected components can be maintained in a total of O(n...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.