Asymptotically efficient in-place merging (2008)
Katajainen, Jyrki, Pasanen, Tomi, Titan, George
http://www.tucs.fi/Publications/proceedings/pKaPaTi95a.php
External heaps combined with effective buffering (2008)
Fadel, R., Jakobsen, K. V., Katajainen, Jyrki, Teuhola, Jukka
Sorting multiset stably in minimum space (2008)
Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jKaPa94a.php
Practical in-place mergesort (2008)
Katajainen, Jyrki, Pasanen, Tomi, Teuhola, Jukka
http://www.tucs.fi/Publications/journals/jKaPaTe96.php
In-Place Sorting with Fewer Moves (2008)
Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jKaPa99a.php
Heaps and Heapsort on Secondary Storage (2008)
Fadel, Ramzi, Jakobsen, Kim Vagn, Katajainen, Jyrki, Teuhola, Jukka
Asymptotically efficient in-place merging (2008)
Geffert, Viliam, Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jGeKaPaa.php
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
Space-Efficient Planar Convex Hull Algorithms (2003)
Herve Bronnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-e#cient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-e#cient...
Space-Efficient Planar Convex Hull Algorithms (2003)
John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-ecient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four space-ecient...
In-Place Planar Convex Hull Algorithms (2002)
John Iacono, Jyrki Katajainen, Pat Morin
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Asymptotically Efficient in-Place Merging (2001)
Viliam Geffert, Jyrki Katajainen, Tomi Pasanen
Two linear-time algorithms for in-place merging are presented. Both algorithms perform at most m(t+1)+n=2 t +o(m) comparisons, where m and n are the sizes of the input sequences, m n, and t = blog 2...
Stable Minimum Space Partitioning in Linear Time (2001)
In the stable 0-1 sorting problem the task is to sort an array of n elements with two distinct values such that equal elements retain their relative input order.
In-Place Sorting With Fewer Moves (2001)
Jyrki Katajainen, Tomi A. Pasanen
It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n= log log n) element moves, and n log 2 n+O(n log log n) comparisons. This is the first in-place sorting...
Practical In-Place Mergesort (2001)
Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola
Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N ) comparisons and 3N log 2 N + O(N ) moves to...
Sorting Multisets Stably in Minimum Space (2001)
We consider the problem of sorting a multiset of size n containing m distinct elements, where the ith distinct element appears n i times. Under the assumption that our model of computation allows...
Supporting Intellectual Work Through Artifact Rendering and Group Review (2000)
: Intellectual teamwork, such as that done by software development teams, is characterized by the intangibility of its subject matter. This can make it dicult for team members and outside...
Efficient Parallel Algorithms for Manipulating Sorted Sets (2000)
The parallel complexity of various operations on sorted sets is studied. Let X and Y be two sorted sets of respective size n and m, n m. Paul, Vishkin, and Wagener [R.A.I.R.O. Informatique...
Performance Engineering Case Study: Heap Construction (1999)
Jesper Bojesen, Jyrki Katajainen, Maz Spork
this paper we study, both analytically and experimentally, the performance of programs that construct a binary heap [Williams 1964] in a hierarchical memory system. Especially, we consider the...
In-Place Sorting With Fewer Moves (1998)
Jyrki Katajainen, Tomi A. Pasanen
. It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n= log log n) element moves, and n log 2 n+O(n log log n) comparisons. This is the first in-place sorting...
Asymptotically Efficient In-Place Merging (1997)
Geffert, Viliam, Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/techreports/TR148.php
. A variant of Heapsort---named Ultimate Heapsort---is presented that sorts n elements in-place in Theta(n log 2 (n+ 1)) worst-case time by performing at most n log 2 n + Theta(n) key comparisons and...
. A variant of Heapsort---named Ultimate Heapsort---is presented that sorts n elements in-place in Theta(n log 2 (n+ 1)) worst-case time by performing at most n log 2 n + Theta(n) key comparisons and...
Worst-Case Efficient External-Memory Priority Queues (1997)
Gerth Stølting Brodal, Im Stadtwald, Jyrki Katajainen
A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which...
Worst-Case Efficient External-Memory Priority Queues (1997)
Gerth Stølting Brodal, Im Stadtwald, Jyrki Katajainen
A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which...
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (the possible values of flow into and out of the terminals)...
Characterizing Multiterminal Flow Networks and (1996)
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (the possible values of flow into and out of the terminals)...
Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees (1994)
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (possible values of flow at the terminals) has two...
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (possible values of flow at the terminals) has two...
Bucketing and filtering in computational geometry /--by Jyrki Katajainen. (1987)
Thesis (doctoral)--University of Turku, 1987.