Jyrki Katajainen: Publications

A. Theses

A3 Bucketing and filtering in computational geometry  more
Jyrki Katajainen
Ph.D. Thesis, Department of Computer Science, University of Turku (1987), vi+120 pp.
(Includes C3, C7, C9, C10, C11, C12; Public discussion November 1987)
A2 On finding minimum spanning trees (Introduction in Finnish)  more
Jyrki Katajainen
Licentiate Thesis, Department of Computer Science, University of Turku (1983), vi+115 pp.
(Includes I1, J1, I3, C2, C4, I4)
A1 Tree automata and context-free languages (in Finnish)
Jyrki Katajainen
Master's Thesis, Department of Mathematics, University of Turku (1980), 58 pp.

B. Books

B1 Reengineering a university department: Promoting the operational change of the computing department at the University of Copenhagen  more
Christopher Derek Curry and Jyrki Katajainen
International Edition, Jyrki Katajainen and Company (2006), xiv+210 pp.

C. Journal papers

C51 All-in-one implementation framework for binary heaps  more
Jyrki Katajainen
Software: Practice and Experience 47,4 (2017), 523–558
C50 Bipartite binomial heaps  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
RAIRO—Theoretical Informatics and Applications (to appear)
C49 Heap construction—50 years later  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
The Computer Journal 60,5 (2017), 657–674
C48 Optimizing binary heaps  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Theory of Computing Systems 61,2 (2017), 606–636
C47 Editorial, SEA 2014 Special Issue  more
Joachim Gudmundsson and Jyrki Katajainen
ACM Journal of Experimental Algorithmics 21 (2016), Article 1.1, 1 p.
C46 Selection from read-only memory with limited workspace  more
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti
Theoretical Computer Science 554 (2014), 64–73
C45 Fat heaps without regular counters  more
Amr Elmasry and Jyrki Katajainen
Discrete Mathematics, Algorithms and Applications 5,2 (2013), Article 1360006, 21 pp.
C44 Weak heaps engineered  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Journal of Discrete Algorithms 23 (2013), 83–97
C43 Two skew-binary numeral systems and one application  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Theory of Computing Systems 50,1 (2012), 185–211
C42 The weak-heap data structure: Variants and applications  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Journal of Discrete Algorithms 16 (2012), 187–205
C41 A compact data structure for representing a dynamic multiset  more
Jyrki Katajainen and Srinivasa Rao Satti
Information Processing Letters 110,23 (2010), 1061–1066
C40 Compressing spatio-temporal trajectories  more
Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong, and Thomas Wolle
Computational Geometry—Theory and Applications 42,9 (2009), 825–841
C39 Two new methods for constructing double-ended priority queues from priority queues  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Computing 83,4 (2008), 193–204
C38 Two-tier relaxed heaps  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Acta Informatica 45,3 (2008), 193–210
C37 Multipartite priority queues  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
ACM Transactions on Algorithms 5,1 (2008), Article 14, 19 pp.
C36 Space-efficient planar convex hull algorithms  more
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, and Godfried Toussaint
Theoretical Computer Science 321,1 (2004), 25–40
C35 Navigation piles with applications to sorting, priority queues, and priority deques  more
Jyrki Katajainen and Fabio Vitale
Nordic Journal of Computing 10,3 (2003), 238–262
C34 Asymptotically efficient in-place merging  more
Viliam Geffert, Jyrki Katajainen, and Tomi A. Pasanen
Theoretical Computer Science 237,1-2 (2000), 159–181
C33 Performance engineering case study: Heap construction  more
Jesper Bojesen, Jyrki Katajainen, and Maz Spork
ACM Journal of Experimental Algorithmics 5 (2000), Article 15, 44 pp.
C32 In-place sorting with fewer moves  more
Jyrki Katajainen and Tomi A. Pasanen
Information Processing Letters 70,1 (1999), 31–37
C31 Heaps and heapsort on secondary storage  more
Ramzi Fadel, Kim Vagn Jakobsen, Jyrki Katajainen, and Jukka Teuhola
Theoretical Computer Science 220,2 (1999), 345–362
C30 Characterizing multiterminal flow networks and computing flows in networks of small treewidth  more
Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde
Journal of Computer and System Sciences 57,3 (1998), 366–375
C29 A reliable randomized algorithm for the closest-pair problem  more
Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen
Journal of Algorithms 25,1 (1997), 19–51
C28 Practical in-place mergesort  more
Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola
Nordic Journal of Computing 3,1 (1996), 27–40
C27 Spørgsmål og svar om el-overfølsomhed  more
Margit Larsson and Jyrki Katajainen
EBD Nyt 10 (1995)
C26 Sorting multisets stably in minimum space  more
Jyrki Katajainen and Tomi A. Pasanen
Acta Informatica 31,4 (1994), 301–313
C25 Finding the maximum in parallel random access machines  more
Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala
Bulletin of the EATCS 52 (1994), 315–334
C24 Space-efficient parallel merging  more
Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson
Informatique Théorique et Applications 27,4 (1993), 295–310
C23 An analysis of the longest match and the greedy heuristics for text encoding  more
Jyrki Katajainen and Timo Raita
Journal of the ACM 39,2 (1992), 281–294
C22 Stable minimum space partitioning in linear time  more
Jyrki Katajainen and Tomi A. Pasanen
BIT 32,4 (1992), 580–585
C21 Lisää tehoa tietokoneisiin — Prosessorit yhteistyöhön  more
Jyrki Katajainen, Ville Leppänen, and Martti Penttonen
Tiede 2000 6 (1992), 16–21
(A preliminary version of I15)
C20 Comparison of algorithms for standard median filtering  more
Martti Juhola, Jyrki Katajainen, and Timo Raita
IEEE Transactions on Signal Processing 39,1 (1991), 204–208
C19 Maksimin määrääminen rinnakkaiskoneissa  more
Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala
Tietojenkäsittelytiede 2 (1991), 36–48
(A preliminary version of C25)
C18 A note on the complexity of trie compaction
Jyrki Katajainen and Erkki Mäkinen
Bulletin of the EATCS 41 (1990), 212–216
C17 Tree compression and optimization with applications  more
Jyrki Katajainen and Erkki Mäkinen
International Journal of Foundations of Computer Science 1,4 (1990), 425–447
C16 A sublogarithmic convex hull algorithm  more
Per-Olof Fjällström, Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson
BIT 30,3 (1990), 378–384
C15 Divide and conquer for the closest-pair problem revisited  more
Jyrki Katajainen, Markku Koppinen, Timo Leipälä, and Olli Nevalainen
International Journal on Computer Mathematics 27,3-4 (1989), 121–132
C14 An approximation algorithm for space-optimal encoding of a text  more
Jyrki Katajainen and Timo Raita
The Computer Journal 32,3 (1989), 228–237
C13 Fast simulation of Turing machines by random access machines  more
Jyrki Katajainen, Jan van Leeuwen, and Martti Penttonen
SIAM Journal on Computing 17,1 (1988), 77–88
C12 Constructing Delaunay triangulations by merging buckets in quadtree order  more
Jyrki Katajainen and Markku Koppinen
Fundamenta Informaticae XI,3 (1988), 275–288
C11 The region approach for computing relative neighbourhood graphs in the Lp metric  more
Jyrki Katajainen
Computing 40,2 (1988), 147–161
C10 A linear expected-time algorithm for computing planar relative neighbourhood graphs  more
Jyrki Katajainen, Olli Nevalainen, and Jukka Teuhola
Information Processing Letters 25,2 (1987), 77–86
C9 An almost naive algorithm for finding relative neighbourhood graphs in Lp metrics  more
Jyrki Katajainen and Olli Nevalainen
Informatique Théorique et Applications 21,2 (1987), 199–215
C8 Syntax-directed compression of program files  more
Jyrki Katajainen, Martti Penttonen, and Jukka Teuhola
Software: Practice and Experience 16,3 (1986), 269–276
C7 Computing relative neighbourhood graphs in the plane  more
Jyrki Katajainen and Olli Nevalainen
Pattern Recognition 19,3 (1986), 221–228
C6 Notes on the complexity of sorting in abstract machines  more
Martti Penttonen and Jyrki Katajainen
BIT 25,4 (1985), 611–622
C5 NP-completeness of the Hamming salesman problem  more
Jarmo Ernvall, Jyrki Katajainen, and Martti Penttonen
BIT 25,1 (1985), 289–292
C4 An alternative for the implementation of Kruskal’s minimal spanning tree algorithm  more
Jyrki Katajainen and Olli Nevalainen
Science of Computer Programming 3,2 (1983), 205–216
C3 On the worst case of a minimal spanning tree algorithm for Euclidean space  more
Jyrki Katajainen
BIT 23,1 (1983), 2–8
C2 Experiments with a closest point algorithm in Hamming space  more
Olli Nevalainen and Jyrki Katajainen
Angewandte Informatik 24,5 (1982), 277–281
C1 Finding minimal spanning trees in a Euclidean coordinate space  more
Olli Nevalainen, Jarmo Ernvall, and Jyrki Katajainen
BIT 21,1 (1981), 46–54

D. Conference papers

D56 Worst-case-efficient dynamic arrays in practice  more
Jyrki Katajainen
Proceedings of the 15th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 9685, Springer (2016), 167–183
D55 An in-place priority queue with O(1) time for push and lg n + O(1) comparisons for pop  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 10th International Computer Science Symposium in Russia, Lecture Notes in Computer Science 9139, Springer-Verlag (2015), 1–15
D54 In-place binary counters  more
Amr Elmasry and Jyrki Katajainen
Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 8087, Springer-Verlag (2013), 349–360
D53 Branchless search programs  more
Amr Elmasry and Jyrki Katajainen
Proceedings of the 12th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 7933, Springer-Verlag (2013), 127–138
D52 Selection from read-only memory with limited workspace  more
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti
Proceedings of the 19th Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 7936, Springer-Verlag (2013), 147–157
D51 Weak heaps and friends: Recent developments  more
Stefan Edelkamp, Amr Elmasry, Jyrki Katajainen, and Armin Weiß
Proceedings of the 24th International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 8288, Springer-Verlag (2013), 1–6
(Stefan’s invited talk)
D50 Priority queues and sorting for read-only data  more
Tetsuo Asano, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation, Lecture Notes in Computer Science 7876, Springer-Verlag (2013), 32–41
D49 Improved address-calculation coding of integer arrays  more
Amr Elmasry, Jyrki Katajainen, and Jukka Teuhola
Proceedings of the 19th International Symposium on String Processing and Information Retrieval, Lecture Notes in Computer Science 7608, Springer-Verlag (2012), 205–216
D48 Branch mispredictions don’t affect mergesort  more
Amr Elmasry, Jyrki Katajainen, and Max Stenmark
Proceedings of the 11th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 7276, Springer-Verlag (2012), 160–171
D47 Fat heaps without regular counters  more
Amr Elmasry and Jyrki Katajainen
Proceedings of the 6th Workshop on Algorithms and Computation, Lecture Notes in Computer Science 7157, Springer-Verlag (2012), 173–185
D46 Lean programs, branch mispredictions, and sorting  more
Amr Elmasry and Jyrki Katajainen
Proceedings of the 6th International Conference on Fun with Algorithms, Lecture Notes in Computer Science 7288, Springer-Verlag (2012), 119–130
D45 Worst-case optimal priority queues via extended regular counters  more
Amr Elmasry and Jyrki Katajainen
Proceedings of the 7th International Computer Science Symposium in Russia, Lecture Notes in Computer Science 7353, Springer-Verlag (2012), 130–142
D44 The weak-heap family of priority queues in theory and praxis  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 18th Computing: The Australasian Theory Symposium, Conferences in Research and Practice in Information Technology 128, Australian Computer Society, Inc. (2012), 103–112
(A preliminary version of C42)
D43 A catalogue of algorithms for building weak heaps  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 23nd International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 7643, Springer-Verlag (2012), 249–262
D42 In-place heap construction with optimized comparisons, moves, and cache misses  more
Jingsen Chen, Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 7464, Springer-Verlag (2012), 259–270
D41 Two constant-factor-optimal realizations of adaptive heapsort  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Proceedings of the 22nd International Workshop on Combinatorial Algorithms, Lecture Notes in Computer Science 7056, Springer-Verlag (2011), 195–208
(A preliminary version of C42)
D40 The Open Graph Archive: A community-driven effort  more
Christian Bachmaier, Franz J. Brandenburg, Philip Effinger, Carsten Gutwenger, Jyrki Katajainen, Karsten Klein, Miro Spönemann, Matthias Stegmaier, and Michael Wybrow
Proceedings of the 19th International Symposium on Graph Drawing, Lecture Notes in Computer Science 7034, Springer-Verlag (2011), 435–440
D39 The magic of a number system  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Proceedings of the 5th International Conference on Fun with Algorithms, Lecture Notes in Computer Science 6099, Springer-Verlag (2010), 156–165
(A preliminary version of C43)
D38 Strictly-regular number system and data structures  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory, Lecture Notes in Computer Science 6139, Springer-Verlag (2010), 26–37
D37 Policy-based benchmarking of weak heaps and their relatives  more
Asger Bruun, Stefan Edelkamp, Jyrki Katajainen, and Jens Rasmussen
Proceedings of the 9th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 6049, Springer-Verlag (2010), 424–435
D36 Adaptable component frameworks: Using vector from the C++ standard library as an example  more
Jyrki Katajainen and Bo Simonsen
Proceedings of the 2009 ACM SIGPLAN Workshop on Generic Programming, ACM (2009), 13–24
D35 Stronger guarantees for standard-library containers  more
Jyrki Katajainen
Oberwolfach Reports, 4,2, Mathematisches Forchungsinstitut Oberwolfach (2007), 1407–1411
D34 Making operations on standard-library containers strongly exception safe  more
Jyrki Katajainen
Proceedings of the 3rd DIKU-IST Joint Workshop on Foundations of Software, Report 07/07, Department of Computer Science, University of Copenhagen (2007), 158–169
D33 Compressing spatio-temporal trajectories  more
Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong, and Thomas Wolle
Proceedings of the 18th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 4835, Springer-Verlag (2007), 763–775
(A preliminary version of C40)
D32 On the power of structural violations in priority queues  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Proceedings of the 13th Computing: The Australasian Theory Symposium, Conferences in Research and Practice in Information Technology 65, Australian Computer Society, Inc. (2007), 45–53
D31 Two-tier relaxed heaps  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
Proceedings of the 17th International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 4288, Springer-Verlag (2006), 308–317
(A preliminary version of C38)
D30 A randomized in-place algorithm for positioning the kth element in a multiset  more
Jyrki Katajainen and Tomi A. Pasanen
Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 2368, Springer-Verlag (2002), 408–417
D29 Performance tuning an algorithm for compressing relational tables  more
Jyrki Katajainen and Jeppe Nejsum Madsen
Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 2368, Springer-Verlag (2002), 398–407
D28 In-place planar convex hull algorithms  more
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, and Godfried Toussaint
Proceedings of the 5th Latin American Theoretical Informatics Symposium, Lecture Notes in Computer Science 2286, Springer-Verlag (2002), 197–205
(A preliminary version of C36)
D27 Experiences with the design and implementation of space-efficient deques  more
Jyrki Katajainen and Bjarke Buur Mortensen
Proceedings of the 5th Workshop on Algorithm Engineering, Lecture Notes in Computer Science 2141, Springer-Verlag (2001), 39–50
D26 Interchanging two segments of an array in a hierarchical memory system  more
Jesper Bojesen and Jyrki Katajainen
Proceedings of the 4th International Workshop on Algorithm Engineering, Lecture Notes in Computer Science 1982, Springer-Verlag (2001), 159–170
D25 Performance engineering case study: Heap construction  more
Jesper Bojesen, Jyrki Katajainen, and Maz Spork
Proceedings of the 3rd International Workshop on Algorithm Engineering, Lecture Notes in Computer Science 1668, Springer-Verlag (1999), 301–315
(A preliminary version of C33)
D24 The Ultimate Heapsort  more
Jyrki Katajainen
Proceedings of the Computing: {T}he 4th Australasian Theory Symposium, Australian Computer Science Communications 20,3, Springer-Verlag Singapore Pte. Ltd. (1998), 87–96
D23 Worst-case efficient external-memory priority queues  more
Gerth Stølting Brodal and Jyrki Katajainen
Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 1432, Springer-Verlag (1998), 107–118
D22 A meticulous analysis of mergesort programs  more
Jyrki Katajainen and Jesper Larsson Träff
Proceedings of the 3rd Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science 1203, Springer-Verlag (1997), 217–228
D21 External heaps combined with effective buffering  more
Ramzi Fadel, Kim Vagn Jakobsen, Jyrki Katajainen, and Jukka Teuhola
Proceedings of the Computing: {T}he 3rd Australasian Theory Symposium, Australian Computer Science Communications 19,2, (1997), 72–78
(A preliminary version of C31)
D20 Finding all nearest smaller values on a distributed memory machine  more
Jyrki Katajainen
Proceedings of the Computing: The 2nd Australasian Theory Symposium, Australian Computer Science Communications 18,3, Computer Science Association (Australia) (1996), 100–107
D19 Constants in parallel sorting  more
Jyrki Katajainen
Proceedings of the 19th Australasian Computer Science Conference, Australian Computer Science Communications 18,1, Computer Science Association (Australia) (1996), 357–366
D18 Space-efficient construction of optimal prefix codes  more
Alistair Moffat, Andrew Turpin, and Jyrki Katajainen
Proceedings of the 5th IEEE Data Compression Conference, IEEE Computer Society Press (1995), 192–201
D17 In-place calculation of minimum-redundacy codes  more
Alistair Moffat and Jyrki Katajainen
Proceedings of the 4th Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science 955, Springer-Verlag (1995), 393–402
D16 Simple parallel algorithms for the replacement edge problem and related problems on minimum spanning trees  more
Jyrki Katajainen and Jesper Larsson Träff
Proceedings of the 18th Australasian Computer Science Conference, Australian Computer Science Communications 17,1, (1995), 254–261
D15 Asymptotically efficient in-place merging  more
Jyrki Katajainen, Tomi A. Pasanen, and George Titan
Proceedings of the 20th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 969, Springer-Verlag (1995), 211–220
(A preliminary version of C34)
D14 A fast and space-economical algorithm for length-limited coding  more
Jyrki Katajainen, Alistair Moffat, and Andrew Turpin
Proceedings of the 6th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science 1004, Springer-Verlag (1995), 12–21
D13 Characterizations of k-terminal flow networks and computing network flows in partial k-trees  more
Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde
Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM and SIAM (1995), 641–649
(A preliminary version of C30)
D12 Practical in-place mergesort  more
Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola
Proceedings of the 7th Finnish Symposium on Computer Science, Report A-1994-1, Department of Computer Science, University of Joensuu (1994), 55–62
(A preliminary version of C28)
D11 Efficient parallel algorithms for manipulating sorted sets  more
Jyrki Katajainen
Proceedings of the 17th Annual Computer Science Conference, Australian Computer Science Communications 16,1, (1994), 281–288
D10 On using type information in syntactical data compression
Jyrki Katajainen and Erkki Mäkinen
Proceedings of the 3rd Symposium on Programming Languages and Software Tools, Department of Computer Science, University of Tartu (1993), 59–65
D9 Improved parallel bucketing algorithms for proximity problems
Torben Hagerup and Jyrki Katajainen
Proceedings of the 26th Annual Hawaii International Conference on System Sciences, II: Software Technology, IEEE Computer Society Press (1993), 318–327
D8 Sorting multisets stably in minimum space  more
Jyrki Katajainen and Tomi A. Pasanen
Proceedings of the 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 621, Springer-Verlag (1992), 410–421
(A preliminary version of C26)
D7 Space-efficient parallel merging  more
Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson
Proceedings of the 4th International PARLE Conference (Parallel Architectures and Languages Europe), Lecture Notes in Computer Science 605, Springer-Verlag (1992), 37–49
(A preliminary version of C24)
D6 In-place linear probing sort  more
Svante Carlsson, Jyrki Katajainen, and Jukka Teuhola
Proceedings of the 9th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 577, Springer-Verlag (1992), 581–587
D5 Local insertion sort revisited  more
Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson
Proceedings of the 2nd International Symposium on Optimal Algorithms, Lecture Notes in Computer Science 401, Springer-Verlag (1989), 239–253
D4 An optimal expected-time parallel algorithm for Voronoi diagrams  more
Christos Levcopoulos, Jyrki Katajainen, and Andrzej Lingas
Proceedings of the 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 318, Springer-Verlag (1988), 190–198
D3 On the encoding of a text with a precomputed dictionary  more
Jyrki Katajainen and Timo Raita
Proceedings of the 3rd Finnish Symposium on Theoretical Computer Science, Report #15, Faculty of Mathematics and Natural Sciences, University of Joensuu (1987), 88–110
(A preliminary version of C14 and C23)
D2 Syntax-directed compression of program files  more
Jyrki Katajainen, Martti Penttonen, and Jukka Teuhola
Proceedings of the 2nd Finnish Summer School on Theoretical Computer Science, Report A38, Department of Computer Science, University of Turku (1985), 60–71
(A preliminary version of C8)
D1 Notes on the complexity of sorting in abstract machines  more
Martti Penttonen and Jyrki Katajainen
Proceedings of the Winter School on Theoretical Computer Science, Finnish Society of Information Processing Science (1984), 206–221
(A preliminary version of C6)

E. Book parts

E2 Applying design patterns to specify the architecture of a generic program library  more
Jyrki Katajainen and Bo Simonsen
Bo Simonsen, Foundations of an adaptable container library, Master's Thesis, Department of Computer Science, University of Copenhagen (2009), 44–69
E1 Interchanging two segments of an array in a hierarchical memory system  more
Jesper Bojesen and Jyrki Katajainen
Jesper Bojesen, Managing memory hierarchies, Master's Thesis, Department of Computer Science, University of Copenhagen (2000), 4–27
(A longer version of D26)

F. Conference abstracts

F6 Seeking for the best priority queue: Lessons learnt  more
Jyrki Katajainen
Algorithm Engineering (Dagstuhl Seminar 13391), Dagstuhl Reports 3,9, Schloss Dagstuhl---Leibniz-Zentrum für Informatik (2014), 74–75
F5 Graph Archive  more
Christian Bachmaier, Franz J. Brandenburg, Philip Effinger, Carsten Gutwenger, Jyrki Katajainen, Karsten Klein, Miro Spönemann, and Michael Wybrow
Graph Drawing with Algorithm Engineering Methods (Dagstuhl Seminar 11191), Dagstuhl Reports 1,5, Schloss Dagstuhl---Leibniz-Zentrum für Informatik (2011), 52–53
F4 Putting your data structure on a diet  more
Hervé Brönnimann, Jyrki Katajainen, and Pat Morin
Proceedings of the 6th STL Workshop, CPH STL Report 2006-8, Department of Computer Science, University of Copenhagen (2006), 3
F3 Top-Down Not-Up Heapsort
Jyrki Katajainen, Jukka Teuhola, and Tomi A. Pasanen
Proceedings of the Algorithm Day in Copenhagen, Report 97/24, Department of Computer Science, University of Copenhagen (1997), 7–9
F2 On abstract modelling of computations
Jyrki Katajainen and Martti Penttonen
Abstracts of Invited Lectures and Short Communications Delivered at the 6th International Colloquium on Numerical Analysis and Computer Science with Applications, Impulse-M (1997), 65
F1 Algorithms for the all-nearest-neighbor problem
Per-Olof Fjällström, Jyrki Katajainen, and Jan Petersson
Abstracts of the 15th IFIP Conference on System Modelling and Optimization: Part I, International Federation for Information Processing (1991), 74–75

G. Errata

G9 Stable minimum space partitioning in linear time: Errata  more
Jyrki Katajainen and Tomi A. Pasanen
Web document (2014)
G8 Branch mispredictions don’t affect mergesort: Errata  more
Amr Elmasry, Jyrki Katajainen, and Max Stenmark
Web document (2014)
G7 Selection from read-only memory with limited workspace: Errata  more
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti
Web document (2014)
G6 Navigation piles with applications to sorting, priority queues, and priority deques: Errata  more
Jyrki Katajainen and Fabio Vitale
Web document (2013)
G5 Fat heaps without regular counters: Errata  more
Jyrki Katajainen
Web document (2012)
G4 Two constant-factor-optimal realizations of adaptive heapsort: Errata  more
Jyrki Katajainen
Web document (2012)
G3 The weak-heap family of priority queues in theory and praxis: Errata  more
Jyrki Katajainen
Web document (2012)
G2 Two-tier relaxed heaps: Errata  more
Jyrki Katajainen
Web document (2012)
G1 The weak-heap data structure: Variants and applications: Errata  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
Web document (2012)

H. Edited publications

H16 Proceedings of the 13th Symposium on Experimental Algorithms  more
Joachim Gudmundsson and Jyrki Katajainen (Editors)
Lecture Notes in Computer Science 8504, Springer (2014), xx+450
H15 Surveys on component-based development  more
Jyrki Katajainen (Editor)
CPH STL Report 2009-5, Department of Computer Science, University of Copenhagen (2009), i+34 pp.
H14 Essays on C++ concepts  more
Jyrki Katajainen (Editor)
CPH STL Report 2008-4, Department of Computer Science, University of Copenhagen (2008), 14 pp.
H13 Proceedings of the 6th STL Workshop  more
Jyrki Katajainen (Editor)
CPH STL Report 2006-8, Department of Computer Science, University of Copenhagen (2006), iv+52 pp.
H12 Project practical data structures and algorithms: Final report  more
Jyrki Katajainen (Editor)
CPH STL Report 2006-4, Department of Computer Science, University of Copenhagen (2006), 9 pp.
H11 Proceedings of the 9th Scandinavian Workshop on Algorithm Theory  more
Torben Hagerup and Jyrki Katajainen (Editors)
Lecture Notes in Computer Science 3111, Springer-Verlag (2004), xi+506
H10 Research proposal: Practical data structures and algorithms  more
Jyrki Katajainen (Editor)
CPH STL Report 2002-8, Department of Computer Science, University of Copenhagen (2002), 6 pp.
H9 Project performance engineering: Final report  more
Jyrki Katajainen (Editor)
CPH STL Report 2002-5, Department of Computer Science, University of Copenhagen (2002), 11 pp.
H8 Research proposal: Software tools for program library development  more
Jyrki Katajainen (Editor)
CPH STL Report 2001-15, Department of Computer Science, University of Copenhagen (2001), 7 pp.
H7 Project proposal: The Copenhagen STL  more
Jyrki Katajainen and Lars Yde (Editors)
CPH STL Report 2000-1, Department of Computer Science, University of Copenhagen (2000), 5 pp.
H6 Proceedings of the Algorithm Day in Copenhagen
Torben Hagerup and Jyrki Katajainen (Editors)
Report 97/24, Department of Computer Science, University of Copenhagen (1997), 28 pp.
H5 Proceedings of the 2nd Copenhagen Conference on Electromagnetic Hypersensitivity  more
Jyrki Katajainen and Bengt Knave (Editors)
Danish Association for the Electromagnetically Hypersensitive (1995)
H4 El-overfølsomhed — problemet eksisterer, eksisterer problemet  more
Lis Henningsen, Else Hynne, Jyrki Katajainen, and Karin Outzen (Editors)
Department of Computer Science, University of Copenhagen (1994), viii+125
H3 Adaptiivisia lajittelualgoritmeja C++ kielellä
Jyrki Katajainen (Editor)
Lecture Notes C10, Department of Computer Science, University of Turku (1990)
H2 Proceedings of the 2nd Finnish Summer School on Theoretical Computer Science
Jyrki Katajainen, Martti Penttonen, and Arto Salomaa (Editors)
Report A38, Department of Computer Science, University of Turku (1985), iii+181 pp.
H1 Systemoinnin seminaariesitelmät
Jyrki Katajainen and Markku Nurminen (Editors)
Lecture Notes C4, Department of Computer Science, University of Turku (1984)

I. Technical reports

I42 All-in-one implementation framework for binary heaps  more
Jyrki Katajainen
CPH STL Report 2015-1, Department of Computer Science, University of Copenhagen (2015), 51 pp.
I41 Memory-adjustable navigation piles with applications to sorting and convex hulls  more
Omar Darwish, Amr Elmasry, and Jyrki Katajainen
E-print arXiv:1510.07185, arXiv.org (2015), 21 pp.
I40 Selection from read-only memory with limited workspace  more
Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti
E-print arXiv:1407.3342, arXiv.org (2014), 16 pp.
(A corrected version of C46)
I39 Strengthened lazy heaps: Surpassing the lower bounds for binary heaps  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
E-print arXiv:1407.3377, arXiv.org (2014), 14 pp.
I38 Seeking for the best priority queue: Lessons learnt  more
Jyrki Katajainen
CPH STL Report 2013-3, Department of Computer Science, University of Copenhagen (2013), 10 pp.
I37 Towards ultimate binary heaps  more
Amr Elmasry and Jyrki Katajainen
CPH STL Report 2013-1, Department of Computer Science, University of Copenhagen (2013), 13 pp.
I36 Worst-case optimal priority queues via extended regular counters  more
Amr Elmasry and Jyrki Katajainen
E-print arXiv:1112.0993, arXiv.org (2011), 23 pp.
I35 The Open Graph Archive: A community-driven effort  more
Christian Bachmaier, Franz J. Brandenburg, Philip Effinger, Carsten Gutwenger, Jyrki Katajainen, Karsten Klein, Miro Spönemann, Matthias Stegmaier, and Michael Wybrow
E-print arXiv:1109.1465, arXiv.org (2011), 10 pp.
I34 Relaxed weak queues and their implementation on a pointer machine  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
CPH STL Report 2010-4, Department of Computer Science, University of Copenhagen (2010), 18 pp.
I33 Mini-project: Safe standard-library containers  more
Jyrki Katajainen
CPH STL Report 2008-2, Department of Computer Science, University of Copenhagen (2008), 6 pp.
I32 Project description: Foundations and tools for building well-behaved systems  more
Cyrille Artho, Claus Jensen, and Jyrki Katajainen
CPH STL Report 2008-5, Department of Computer Science, University of Copenhagen (2008), 7 pp.
I31 Project proposal: Associative containers with strong guarantees  more
Jyrki Katajainen
CPH STL Report 2007-4, Department of Computer Science, University of Copenhagen (2007), 39 pp.
I30 Putting your data structure on a diet  more
Hervé Brönnimann, Jyrki Katajainen, and Pat Morin
CPH STL Report 2007-1, Department of Computer Science, University of Copenhagen (2007), 22 pp.
I29 Experimental evaluation of local heaps  more
Claus Jensen, Jyrki Katajainen, and Fabio Vitale
CPH STL Report 2006-1, Department of Computer Science, University of Copenhagen (2006), 25 pp.
I28 An experimental evaluation of navigation piles  more
Claus Jensen and Jyrki Katajainen
CPH STL Report 2006-3, Department of Computer Science, University of Copenhagen (2006), 16 pp.
I27 Generic algorithm for 0-1 sorting  more
Gianni Franceschini and Jyrki Katajainen
CPH STL Report 2006-5, Department of Computer Science, University of Copenhagen (2006), 16 pp.
I26 Efficiency of various forms of red-black trees  more
Hervé Brönnimann and Jyrki Katajainen
CPH STL Report 2006-2, Department of Computer Science, University of Copenhagen (2006), 13 pp.
I25 Research proposal: Generic programming—algorithms and tools  more
Jyrki Katajainen
CPH STL Report 2005-5, Department of Computer Science, University of Copenhagen (2005), 9 pp.
I24 Project proposal: A meldable, iterator-valid priority queue  more
Jyrki Katajainen
CPH STL Report 2005-1, Department of Computer Science, University of Copenhagen (2005), 37 pp.
I23 Relaxed weak queues: An alternative to run-relaxed heaps  more
Amr Elmasry, Claus Jensen, and Jyrki Katajainen
CPH STL Report 2005-2, Department of Computer Science, University of Copenhagen (2005), 23 pp.
I22 An extended truth about heaps  more
Claus Jensen, Jyrki Katajainen, and Fabio Vitale
CPH STL Report 2003-5, Department of Computer Science, University of Copenhagen (2003), 16 pp.
I21 Instructions to use DIKU style files  more
Jyrki Katajainen and Kimmo Raatikainen
CPH STL Report 2001-1, Department of Computer Science, University of Copenhagen (2001--2014), 7 pp.
I20 Supporting intellectual work through artifact rendering and group review  more
Lars Yde and Jyrki Katajainen
Report 00/11, Department of Computer Science, University of Copenhagen (2000), 14 pp.
I19 Worst-case efficient external-memory priority queues  more
Gerth Stølting Brodal and Jyrki Katajainen
Report 97/25, Department of Computer Science, University of Copenhagen (1997), 16 pp.
(An extended version of D23)
I18 Experiments with universal hashing  more
Jyrki Katajainen and Michael Lykke
Report 96/8, Department of Computer Science, University of Copenhagen (1996), 17 pp.
(Presented at the 5th DIMACS Implementation Challenge, Priority Queues, Dictionaries, and Multi-Dimensional Point Sets)
I17 Parallel tree slicing
Jyrki Katajainen, Mikkel Thorup, and Jesper Larsson Träff
Report 95/13, Department of Computer Science, University of Copenhagen (1995), 5 pp.
I16 Tree slicing based on tree contraction
Jyrki Katajainen, Mikkel Thorup, and Jesper Larsson Träff
Report 94/30, Department of Computer Science, University of Copenhagen (1994), 9 pp.
I15 More power to computers by parallel computation  more
Jyrki Katajainen, Ville Leppänen, and Martti Penttonen
Report 94/29, Department of Computer Science, University of Copenhagen (1994), 11 pp.
I14 A note on the greedy method for computing relative neighbours
Jyrki Katajainen and Richard B. Tan
Report 93/12, Department of Computer Science, University of Copenhagen (1993), 8 pp.
I13 Two theorems on the parallel construction of convex hulls  more
Jyrki Katajainen
Report 93/23, Department of Computer Science, University of Copenhagen (1993), 10 pp.
I12 Stable minimum space partitioning in linear time  more
Jyrki Katajainen and Tomi A. Pasanen
Report 92/4, Department of Computer Science, University of Copenhagen (1992), 9 pp.
(A preliminary version of C22)
I11 Algorithms for the all-nearest-neighbor problem
Per-Olof Fjällström, Jyrki Katajainen, and Jan Petersson
Report 92/2, Department of Computer Science, University of Copenhagen (1992), 41 pp. 5 app.pp.
(A full version of F1)
I10 Rinnakkaisalgoritmit (Luvut 1-4)
Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala
Lecture Notes C9, Department of Computer Science, University of Turku (1990), 77 pp.
I9 A Prolog prototype of a syntax-directed compression system
Jyrki Katajainen, Martti Penttonen, and Jukka Teuhola
Manual D31, Department of Computer Science, University of Turku (1988), 14 pp. 5 app.pp.
I8 On the encoding of a text with a precomputed dictionary  more
Jyrki Katajainen and Timo Raita
Manuscript B39, Department of Computer Science, University of Turku (1986), 40 pp.
(A full version of D3)
I7 Comparison of algorithms for standard median filtering  more
Martti Juhola, Jyrki Katajainen, and Timo Raita
Manuscript B44, Department of Computer Science, University of Turku (1986), 31 pp. 36 app.pp.
(An extended version of C20)
I6 A note on systems of finite sets satisfying an intersection condition
Jyrki Katajainen and Markku Koppinen
Manuscript B36, Department of Computer Science, University of Turku (1985), 10 pp.
I5 On the relationship between minimum matchings and Delaunay graphs in the Lp-metric
Jyrki Katajainen
Report A42, Department of Computer Science, University of Turku (1985), 10 pp.
I4 An implementation of Cheriton-Tarjan’s minimal spanning tree algorithm using ordered subsets  more
Jyrki Katajainen
Report A35, Department of Computer Science, University of Turku (1983), 10 pp. 10 app.pp.
I3 On the worst case of a minimal spanning tree algorithm for Euclidean space  more
Jyrki Katajainen
Report A34, Department of Computer Science, University of Turku (1982)
(A preliminary version of C3)
I2 Simulointi
Jyrki Katajainen
Lecture Notes, Department of Computer Science, University of Turku (1982), 81 pp.
I1 A minimal spanning tree algorithm for a point set in Euclidean space  more
Jarmo Ernvall, Jyrki Katajainen, and Olli Nevalainen
Report A28, Department of Computer Science, University of Turku (1980)
(A preliminary version of C1)

J. Computer programs

J17 Dynamic-array kernels  more
Jyrki Katajainen
CPH STL Report 2016-2, Department of Computer Science, University of Copenhagen (2016), 100 pp.
J16 Heap-construction programs  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
CPH STL Report 2016-1, Department of Computer Science, University of Copenhagen (2016), 54 pp.
J15 All-in-one implementation framework for binary heaps: Electronic appendix  more
Jyrki Katajainen
CPH STL Report 2015-2, Department of Computer Science, University of Copenhagen (2015), 111 pp.
J14 Sorting programs executing fewer branches  more
Jyrki Katajainen
CPH STL Report 2014-1, Department of Computer Science, University of Copenhagen (2014), 37 pp.
J13 Conceptual frameworks for constructing iterators for compound data structures—Electronic appendix I: Component-iterator and rank-iterator classes  more
Jyrki Katajainen and Andreas Milton Maniotis
CPH STL Report 2012-3, Department of Computer Science, University of Copenhagen (2012), 47 pp.
J12 Branchless search programs: Electronic appendix  more
Jyrki Katajainen
CPH STL Report 2012-1, Department of Computer Science, University of Copenhagen (2012--2013), 30 pp.
J11 A catalogue of weak-heap programs  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
CPH STL Report 2012-2, Department of Computer Science, University of Copenhagen (2012--2013), 42 pp.
J10 Weak-heap and weak-queue frameworks: Source code  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
CPH STL Report 2011-2, Department of Computer Science, University of Copenhagen (2011--2012), 81 pp.
J9 Adaptive heapsort: Source code  more
Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen
CPH STL Report 2011-1, Department of Computer Science, University of Copenhagen (2011--2015), 28 pp.
J8 Fat heaps: Source code  more
Amr Elmasry and Jyrki Katajainen
CPH STL Report 2010-2, Department of Computer Science, University of Copenhagen (2010--2011), 54 pp.
J7 Vector framework: Electronic appendix  more
Jyrki Katajainen and Bo Simonsen
CPH STL Report 2009-4, Department of Computer Science, University of Copenhagen (2009), 67 pp.
J6 Priority-queue frameworks: Programs  more
Jyrki Katajainen
CPH STL Report 2009-7, Department of Computer Science, University of Copenhagen (2009), ii+118 pp.
J5 Experiences with the design and implementation of space-efficient deques  more
Jyrki Katajainen and Bjarke Buur Mortensen
CPH STL Report 2001-7, Department of Computer Science, University of Copenhagen (2001), 47 pp.
(An extended version of D27)
J4 Sorting & Searching Experimentarium  more
Svante Carlsson, Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola
Web document (1997)
J3 Three programs for computing relative neighbourhood graphs in the plane  more
Jyrki Katajainen and Olli Nevalainen
Manual D29, Department of Computer Science, University of Turku (1985), 4 pp. 16 app.pp.
J2 Some programs for finding the minimal spanning forest of a graph  more
Jyrki Katajainen
Manual D28, Department of Computer Science, University of Turku (1984), 2 pp. 16 app.pp.
J1 An implementation of an algorithm for finding minimal spanning trees in a Euclidean coordinate space  more
Jyrki Katajainen
Manual D22, Department of Computer Science, University of Turku (1981), 6 pp. 10 app.pp.
This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2017-09-26.