Change search
Refine search result
1 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Chen, Jingsen
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Edelkamp, Stefan
    Faculty 3-Mathematics and Computer Science, University of Bremen.
    Elmasry, Amr
    Department of Computer Science, University of Copenhagen.
    Katajainen, Jyrki
    Department of Computer Science, University of Copenhagen.
    In-place heap construction with optimized comparisons, moves, and cache misses2012In: Mathematical foundations of computer science 2012: 37th international symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012 : proceedings / [ed] Branislav Rovan; Vladimiro Sassone ; Peter Widmayer, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2012, p. 259-270Conference paper (Refereed)
    Abstract [en]

    We show how to build a binary heap in-place in linear time by performing ~ 1.625n element comparisons, at most ~ 2.125n element moves, and ~ n/B cache misses, where n is the size of the input array, B the capacity of the cache line, and ~ f(n) approaches f(n) as n grows. The same bound for element comparisons was derived and conjectured to be optimal by Gonnet and Munro; however, their procedure requires Θ(n) pointers and does not have optimal cache behaviour. Our main idea is to mimic the Gonnet-Munro algorithm by converting a navigation pile into a binary heap. To construct a binary heap in-place, we use this algorithm to build bottom heaps of size and adjust the heap order at the upper levels using Floyd's sift-down procedure. On another frontier, we compare different heap-construction alternatives in practice.

  • 2.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Computing maximum-scoring segments optimally2007Report (Other academic)
    Abstract [en]

    Given a sequence of length n, the problem studied in this report is to find a set of k disjoint subsequences of consecutive elements such that the total sum of all elements in the set is maximized. This problem arises in the analysis of DNA sequences. The previous best known algorithm requires time proportional to n times the inverse Ackermann function of (n,n), in the worst case. We present a linear-time algorithm, which is optimal, for this problem.

  • 3.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Ranking k maximum sums2007In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 377, no 1-3, p. 229-237Article in journal (Refereed)
    Abstract [en]

    Given a sequence of n real numbers and an integer parameter k, the problem studied in this paper is to compute k subsequences of consecutive elements with the sums of their elements being the largest, the second largest, and the kth largest among all possible range sums of the input sequence. For any value of k, 1 <= k <= n (n + 1)/2, we design a fast algorithm that takes O (n + k log n) time in the worst case to compute and rank all such subsequences. We also prove that our algorithm is optimal for k = O (n) by providing a matching lower bound.Moreover, our algorithm is an improvement over the previous results on the maximum sum subsequences problem (where only the subsequences are requested and no ordering with respect to their relative sums will be determined).Furthermore, given the fact that we have computed the fth largest sums, our algorithm retrieves the (l + 1)th largest sum in O (log n) time, after O (n) time of preprocessing.

  • 4.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Computing maximum-scoring segments in almost linear time2006Report (Other academic)
    Abstract [en]

    Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires n log n time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(n a(n, n) ) time in the worst case, where a(n,n) is the inverse Ackermann function.

  • 5.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Computing maximum-scoring segments in almost linear time2006In: Computing and Combinatorics: 12th annual international conference, COCOON 2006, Taipei, Taiwan, August 15 - 18, 2006 ; proceedings / [ed] Danny Z. Chen, Encyclopedia of Global Archaeology/Springer Verlag, 2006, p. 255-264Conference paper (Refereed)
    Abstract [en]

    Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires Θ(n log n) time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(nα(n, n)) time in the worst case, where α(n, n) is the inverse Ackermann function.

  • 6.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Efficient algorithms for k maximum sums2006In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 46, no 1, p. 27-41Article in journal (Refereed)
    Abstract [en]

    We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers {x1,x2,...,xn} and an integer parameter k, 1 ≤ k ≤ 1/2n(n-1),the problem involves finding the k largest values of ∑ℓ=ijxℓ for 1 ≤ i ≤ j ≤ n.The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a Θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in O(min {k+nlog2n,n√k} ) time in the worst case. Our algorithm is optimal for k = Ω(n log 2 n) and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well

  • 7.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    A note on ranking k maximum sums2005Report (Other academic)
    Abstract [en]

    In this paper, we design a fast algorithm for ranking the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem is to compute k subsequences of consecutive elements with the sums of their elements being the largest, second largest, ..., and the k:th largest among all possible range sums. For any value of k, 1 <= k <= n(n+1)/2, our algorithm takes O(n + k log n) time in the worst case to rank all such subsequences. Our algorithm is optimal for k <= n.

  • 8.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Computing the k maximum subarrays fast2004Report (Other academic)
    Abstract [en]

    We study the problem of computing the k maximum sum subarrays. Given an array of real numbers and an integer, k, the problem involves finding the k largest values of the sum from i to j of the array, for any i and j. The problem for fixed k=1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. In this paper, we develop an algorithm requiring time proportional to n times square root of k for an array of length n. Moreover, for two-dimensional version of the problem, which computes the k largest sums over all rectangular subregions of an m times n array of real numbers, we show that it can be solved efficiently in the worst case as well.

  • 9.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Efficient algorithms for k maximum sums2004In: Algorithms and Computation: 15th International Symposium, ISAAC 2004 / [ed] Rudolf Fleischer; Gerhard Trippen, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2004, p. 137-148Conference paper (Refereed)
    Abstract [en]

    We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers (x1,x2,⋯,xn) and an integer parameter k, l ≤ k ≤ 1/2n(n -1), the problem involves finding the k largest values of Σl=ij xl for 1 ≤ i ≤ j ≤ n. The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a θ(nk)-time algorithm for the k maximum sum subsequences problem. In this paper, we design efficient algorithms that solve the above problem in O (min{k + n log2 n, n √k}) time in the worst case. Our algorithm is optimal for k ≥ n log2 n and improves over the previously best known result for any value of the user-defined parameter k. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well

  • 10.
    Bengtsson, Fredrik
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Chen, Jingsen
    Space-efficient range-sum queries in OLAP2004In: Data Warehousing and Knowledge Discovery. Proceedings: 6th international conference, DaWaK 2004, Zaragoza, Spain, September 1 - 3, 2004 : proceedings / [ed] Yahiko Kambayashi; Mukesh Mohania; Wolfram Wöß, Encyclopedia of Global Archaeology/Springer Verlag, 2004, p. 87-96Conference paper (Refereed)
    Abstract [en]

    In this paper, we present a fast algorithm to answer range-sum queries in OLAP data cubes. Our algorithm supports constant-time queries while maintaining sub-linear time update and using minimum space. Furthermore, we study the trade-off between query time and update time. The complexity for query is O(2ℓd) and for updates O((2ℓ2ℓ√n)d) on a data cube of nd elements, where ℓ is a trade-off parameter. Our algorithm improve over previous best known results

  • 11.
    Carlsson, Svante
    et al.
    Luleå University of Technology.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Mattsson, Christer
    Quality Laboratories AB, IDEON Research Park, S-223 70, Lund.
    Heaps with bits1996In: Theoretical Computer Science, ISSN 0304-3975, E-ISSN 1879-2294, Vol. 164, no 1-2, p. 1-12Article in journal (Refereed)
    Abstract [en]

    We show how to improve the complexity of heap operations and heapsort using extra bits. We first study the parallel complexity of implementing priority queue operations on a heap. The tradeoff between the number of extra bits used, the number of processors available, and the parallel time complexity is derived. While inserting a new element into a heap in parallel can be done as fast as parallel searching in a sorted list, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The models of parallel computation used are the CREW PRAM and the CRCW PRAM. Our results improve those of previously known algorithms. Moreover, we study a variant, the fine heap, of the traditional heap structure. A fast algorithm for constructing this new data structure is designed using an interesting technique, which is also used to develop an improved heapsort algorithm. Our variation of heapsort is faster than I. Wegener's (1993) heapsort and requires less extra space.

  • 12.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    An efficient construction algorithm for a class of implicit double-ended priority queues1995In: Computer journal, ISSN 0010-4620, E-ISSN 1460-2067, Vol. 38, no 10, p. 818-821Article in journal (Refereed)
    Abstract [en]

    Priority queues and double-ended priority queues are fundamental data types in Computer Science, and various data structures have been proposed to implement them. In particular, diamond deques, interval heaps, min-max-pair heaps, and twin-heaps provide implicit structures for double-ended priority queues. Although these heap-like structures are essentially the same when they are presented in an abstract manner, they possess different implementations and thus have different construction algorithms. In this paper, we present a fast algorithm for building these data structures. Our results improve over previously fast known algorithms.

  • 13.
    Carlsson, Svante
    et al.
    Luleå tekniska universitet.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Heap construction: Optimal in both worst and average cases?1995In: Algorithms and Computations: 6th International Symposium, ISAAC '95 Cairns, Australia, December 4-6, 1995 Proceedings / [ed] John Staples, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1995, p. 254-263Conference paper (Refereed)
    Abstract [en]

    We investigate the complexity of constructing heaps. The heap construction problem has been extensively studied. However, there was no algorithm for building heaps that is optimal in both the worst and average cases simultaneously. In particular, the worst-case fastest algorithm, proposed by Gonnet and Munro, takes 1.625n comparisons to build an n-element heap (with an average cost of 1.5803n comparisons). The best known average-case upper bound of 1.5212n comparisons was derived by McDiarmid and Reed, which has a worst-case performance of 2n comparisons. Both algorithms require extra space and were conjectured to be optimal respectively in the worst and the average case. In this paper, we design a heap construction algorithm that takes at most 1.625n and 1.500n comparisons in the worst and average cases, respectively. Our algorithm not only improves over the previous best known average-case result by McDiarmid and Reed, but also achieves the best known worst-case upper bound due to Gonnet and Munro. Moreover, we also show that a heap on n elements can be constructed in-situ using at most 1.528n comparisons on average and 2n comparisons in the worst case. This is only 0.007n comparisons more than that of McDiarmid and Reed's algorithm, while the latter needs n bits of extra space.

  • 14.
    Chen, Jingsen
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Carlsson, Svante
    Luleå tekniska universitet.
    Searching rigid data structures1995In: Computing and Combinatorics: First Annual International Conference, COCOON '95 Xi'an, China, August 24-26, 1995 Proceedings / [ed] Ding-Zhu Du, Encyclopedia of Global Archaeology/Springer Verlag, 1995, p. 446-451Conference paper (Refereed)
    Abstract [en]

    We study the exact complexity of searching for a given element in a rigid data structure (i.e., an implicit data structure consistent with a fixed family of partial orders). In particular, we show how the ordering information available in the structure facilitates the search operation. Some general lower bounds on the search complexity are presented, which apply to concrete rigid data structures as well. Optimal search algorithms for certain rigid structures are also developed. Moreover, we consider a general problem of searching for a number of elements in a given set. Non-trivial lower bounds are derived and efficient search algorithms are constructed.

  • 15.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Average cost to produce partial orders1994In: Algorithms and Computation: 5th International Symposium, ISAAC '94 Beijing, P. R. China, August 25-27, 1994 Proceedings / [ed] Ding-Zhu Du, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 155-163Conference paper (Refereed)
    Abstract [en]

    We study the average-case complexity of partial order productions. Any comparison-based algorithm for solving problems in computer science can be viewed as the partial order production. The productions of some specific partial orders, such as sorting, searching, and selection, have received much attention in the past decades. As to arbitrary partial orders, very little is known about the inherent complexity of their productions. In particular, no non-trivial average-case lower bounds were known. By combining information-theoretic lower bounds with adversary-based arguments, we present some non-trivial average-case lower bounds for the productions of arbitrary partial orders. More precisely, we first demonstrate a counter-example to some intuition about lower bounds on partial order productions, and then present some simple lower bounds. By utilizing adversaries which were originally constructed for deriving worst-case lower bounds, we prove non-trivial average-case lower bounds for partial order productions. Our lower-bound techniques of mixing the information-theoretical and adversary-based approaches are interesting, as well as the lower-bound results obtained. Moreover, several conjectures concerning the production complexity of partial orders are answered. Motivating from the selection problem and from the design of efficient algorithms, we also investigate average-case cost for producing many isomorphic copies simultaneously of some partial order.

  • 16.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Parallel heap construction using multiple selection1994In: Parallel Processing: CONPAR 94 - VAPP VI Third Joint International Conference on Vector and Parallel Processing Linz, Austria, September 6-8, 1994 Proceedings / [ed] Bruno Buchberger, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 371-380Conference paper (Refereed)
    Abstract [en]

    We consider the problem of constructing data structures that implement priority queues (viz. the heap) and double-ended priority queues (namely, the twin-heap, the min-max heap, and the deap) quickly and optimally in parallel. Whereas all these heap-like structures can be built in linear sequential time, we show in this paper that the construction problem can be solved in O(log n·log* n/log log n) time using n·log log n/log n·log * n processors in the Arbitrary CRCW PRAM model. Moreover, by applying random sampling techniques, we reduce the construction time to O with probability ≥ 1-n-c for some constant c>0. As a by-product, we also investigate the parallel complexity of the multiple selection problem. The problem is to select a subset of elements having specified ranks from a given set. We design optimal solutions to the problem with respect to various models of parallel computation.

  • 17.
    Carlsson, Svante
    et al.
    Luleå tekniska universitet.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Some lower bounds for comparison-based algorithms1994In: Algorithms - ESA '94: Second Annual European Symposium Utrecht, The Netherlands, September 26-28, 1994 Proceedings / [ed] Jan van Leeuwen, Encyclopedia of Global Archaeology/Springer Verlag, 1994, p. 106-117Conference paper (Refereed)
    Abstract [en]

    Any comparison-based algorithm for solving a given problem can be viewed as a partial order production. The productions of some particular partial orders, such as sorting and selection, have received much attention in the past decades. As to general partial orders, very little is known about the inherent complexity of their productions. This paper investigates how different sequences of comparisons affect the complexity of the production. We first disprove a folk theorem stating that there always exists an optimal algorithm for producing a partial order that involves the maximum number of disjoint comparisons between singleton elements. We also present some algorithmic properties of partial orders, which demand that any optimal production algorithm must make the all possible disjoint comparisons. Moreover, we show how to and when one can save comparisons in producing a given partial order by constructing many isomorphic copies of the partial order simultaneously or by providing extra elements. Furthermore, the techniques obtained and the results presented have been successful applied to investigate the problem of constructing data structures, resulting in efficient algorithms and tight lower bounds.

  • 18.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    A framework for constructing heap-like structures in-place1993In: Algorithms and Computation: 4th International Symposium, ISAAC '93 Hong Kong, December 15-17, 1993 Proceedings / [ed] K.W. Ng, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1993, p. 118-127Conference paper (Refereed)
    Abstract [en]

    Priority queues and double-ended priority queues are fundamental data types in computer science. Several implicit data structures have been proposed for implementing the queues, such as heaps, min-max heaps, deaps, and twin-heaps. Over the years the problem of constructing these heap-like structures has received much attention in the literature, but different structures possess different construction algorithms. In this paper, we present a uniform approach for building the heap-like data structures in-place. The study is carried out by investigating hardest instances of the problem and developing an algorithmic paradigm for the construction. Our paradigm produces comparison- and space-efficient construction algorithms for the heaplike structures, which improve over those previously fast known algorithms.

  • 19. Chen, Jingsen
    Studies on partial order productions1993Doctoral thesis, comprehensive summary (Other academic)
  • 20. Chen, Jingsen
    Computing and ranking measures of presortedness1992In: International Journal of Computer Mathematics, ISSN 0020-7160, E-ISSN 1029-0265, Vol. 46, no 1-2, p. 39-49Article in journal (Refereed)
    Abstract [en]

    To take advantage of existing order in a sequence when sorting, we consider the problem of evaluating the value of a metric function that estimates the quantity of the order information. A number of algorithms for computing such measures of presortedness are presented. While showing that some measures are linear computable, we demonstrate that for any measure M and for any presortedness sequence X, the value of M(X) can be computed (or approximated) efficiently using a M-adaptive sorting algorithm. The lower bounds on computing measures of presortedness are also given. The method for comparing different presortedness measures, which helps to understand the relationship between different measures and to examine the degree of the sortedness in a sequence with respect to measures, is discussed. We proposed some results that are useful for relating combinatorial properties of the measures to their algorithmic properties

  • 21.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Constructing priority queues and deques optimally in parallel1992In: IFIP transactions. Computer science and technology, ISSN 0926-5473, Vol. A12, p. 275-83Article in journal (Refereed)
    Abstract [en]

    The author investigates the parallel complexity of constructing data structures that implement priority queues (viz. the heap) and double-ended priority queues (namely, the twin-heap, the min-max heap, and the deap). The study is carried out by developing cost optimal parallel deterministic algorithms of time complexity Θ(log log n) and randomized algorithms of time complexity Θ(α(n)) with probability that converges rapidly to one on the parallel comparison tree model, where α(n) is the inverse Ackermann function. The author also describes constant-time parallel algorithms for the constructions with n1+∈ processors for any constant ∈>0 on the same model. Furthermore, the author designs optimal Θ(log n)-time EREW-PRAM algorithms for constructing double-ended priority queue structures

  • 22.
    Chen, Jingsen
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Levcopoulos, Christos
    Lunds universitet.
    Improved parallel sorting of presorted sequences1992In: Parallel Processing: CONPAR 92-VAPP V: Second Joint International Conference on Vector and Parallel Processing Lyon, France, September 1-4, 1992 Proceedings, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1992, p. 539-544Conference paper (Refereed)
    Abstract [en]

    An adaptive parallel sorting algorithm is presented, which is cost optimal with respect to the number of oscillations in a sequence (Osc). More specifically, the algorithm sorts any sequence X of length n in time O(log n) by using O(n/log n · log Osc(X)/n) CRCW PRAM processors. This is the first adaptive parallel sorting algorithm that is cost optimal with respect to Osc and, hence, it is also optimal with respect to both the number of inversions (Inv) and the number of runs (Runs) in the sequence. Our result improves previous results on adaptive parallel sorting.

  • 23. Chen, Jingsen
    Merging and splitting priority queues and deques in parallel1992In: Theory of Computing and Systems: ISTCS '92, Israel Symposium Haifa, Israel, May 27-28, 1992 Proceedings, Encyclopedia of Global Archaeology/Springer Verlag, 1992, p. 1-11Conference paper (Refereed)
    Abstract [en]

    We investigate the parallel complexity of merging priority queues and double-ended priority queues (priority deques, for short). The implicit data structures that implement the queues studied in this paper are the heap, the twin-heap, the min-max heap, and the deap. It is known that heaps can be merged sequentially in sublinear time whereas merging min-max heaps requires linear sequential time. In this paper, we design efficient O(log n)-time parallel algorithms to merge two priority queue or deque structures of the same type on n and k elements (n≥k), respectively, which achieves the optimal speed-up. More precisely, two heaps of sizes n and k can be merged in O(log n) time with log k processors. Moreover, a related problem of splitting a heap on n elements into two heaps of sizes k and n-k is solved in O(log n) parallel time with log n processors, which also achieves the optimal speed-up. For the merge operation on priority deques, we show that the problem of merging twin-heaps can be solved in the same complexity as that for heaps both sequential and in parallel. Algorithms for merging two min-max heaps or two deaps of sizes n and k are demonstrated, which achieves a parallel time of O(log n) with k/log n+log k processors. The study of parallel solution to the problem of merging deaps also provides us with the first serial deap merging algorithm of time complexity O(k+log n·log k). The parallel computation model used in this paper is the EREW PRAM (Exclusive-Read Exclusive-Write Parallel Random Access Machine).

  • 24.
    Carlsson, Svante
    et al.
    Luleå tekniska universitet.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    On partitions and presortedness of sequences1992In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 29, no 3, p. 267-280Article in journal (Refereed)
    Abstract [en]

    To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of an adaptive sorting algorithm Skiena'sMelsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra'sSmoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we also propose some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well.

  • 25.
    Chen, Jingsen
    et al.
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Carlsson, Svante
    Luleå tekniska universitet.
    Parallel complexity of heaps and min-max heaps1992In: LATIN '92: 1st Latin American Symposium on Theoretical Informatics, São Paulo, Brazil, April 6 - 10, 1992 proceedings / [ed] Imre Simon, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1992, p. 108-116Conference paper (Refereed)
    Abstract [en]

    We study parallel solutions to the problem of implementing priority queues and priority deques. It is known that data structures for the implementation (e.g., the heap, the minmax heap, and the deap) can be constructed in linear sequential time. In this paper, we design optimal Ω((log log n)2) time parallel algorithms with n/(log logn)2 processors for the constructions on the parallel comparison tree model. For building heaps in parallel, our algorithm improves the previous best result of Ω(log n) time with n/log n processors. For building min-max heaps and deaps, our algorithms are the first attempt to design parallel algorithms for constructing the data structures of the priority deque that are cost optimal.

  • 26.
    Carlsson, Svante
    et al.
    Luleå tekniska universitet.
    Chen, Jingsen
    Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
    Parallel constructions of heaps and min-max heaps1992In: Parallel Processing Letters, ISSN 0129-6264, Vol. 2, no 4, p. 311-320Article in journal (Refereed)
    Abstract [en]

    The authors study parallel solutions to the problem of implementing priority queues and priority deques. It is known that data structures for the implementation (e.g. the heap, the min-max heap, and the deap) can be constructed in linear sequential time. They design optimal Θ((log log n)2) time parallel algorithms with n/(loglogn)2 processors for the constructions in the parallel comparison tree model

  • 27. Carlsson, Svante
    et al.
    Chen, Jingsen
    An optimal parallel adaptive sorting algorithm1991In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 39, no 4, p. 195-200Article in journal (Refereed)
    Abstract [en]

    We consider the problem of designing optimal parallel algorithms for sorting presorted sequences. To evaluate the existing order in an input sequence, we use the number of the maximal ascending consecutive subsequences, Runs. in the sequence as a measure of presortedness. An adaptive parallel sorting algorithm is presented, which sorts a sequence X of length n inO(logn·log Runs(X)) time by using ... processors in the EREW PRAM model of computation. It is the first adaptive parallel sorting algorithm that is cost optimal with respect to Runs.

  • 28. Carlsson, Svante
    et al.
    Chen, Jingsen
    Strothotte, Thomas
    A note on the construction of the data structure "deep"1989In: Information Processing Letters, ISSN 0020-0190, E-ISSN 1872-6119, Vol. 31, no 6, p. 315-317Article in journal (Refereed)
1 - 28 of 28
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf