Jyrki Katajainen: Publications

A. Theses

A₃	Bucketing and filtering in computational geometry more Jyrki Katajainen Ph.D. Thesis, Department of Computer Science, University of Turku (1987), vi+120 pp. (Includes C₃, C₇, C₉, C₁₀, C₁₁, C₁₂; Public discussion November 1987)
A₂	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 I₁, J₁, I₃, C₂, C₄, I₄)
A₁	Tree automata and context-free languages (in Finnish) Jyrki Katajainen Master's Thesis, Department of Mathematics, University of Turku (1980), 58 pp.

B. Books

B₁	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

C₅₂	Convex-hull algorithms: Implementation, testing, and experimentation more Ask Neve Gamby and Jyrki Katajainen Algorithms 11,12 (2018), Article 195
C₅₁	All-in-one implementation framework for binary heaps more Jyrki Katajainen Software: Practice and Experience 47,4 (2017), 523–558
C₅₀	Bipartite binomial heaps more Amr Elmasry, Claus Jensen, and Jyrki Katajainen RAIRO—Theoretical Informatics and Applications 51,3 (2017), 121–133
C₄₉	Heap construction—50 years later more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen The Computer Journal 60,5 (2017), 657–674
C₄₈	Optimizing binary heaps more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Theory of Computing Systems 61,2 (2017), 606–636
C₄₇	Editorial, SEA 2014 Special Issue more Joachim Gudmundsson and Jyrki Katajainen ACM Journal of Experimental Algorithmics 21 (2016), Article 1.1, 1 p.
C₄₆	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
C₄₅	Fat heaps without regular counters more Amr Elmasry and Jyrki Katajainen Discrete Mathematics, Algorithms and Applications 5,2 (2013), Article 1360006, 21 pp.
C₄₄	Weak heaps engineered more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Journal of Discrete Algorithms 23 (2013), 83–97
C₄₃	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
C₄₂	The weak-heap data structure: Variants and applications more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Journal of Discrete Algorithms 16 (2012), 187–205
C₄₁	A compact data structure for representing a dynamic multiset more Jyrki Katajainen and Srinivasa Rao Satti Information Processing Letters 110,23 (2010), 1061–1066
C₄₀	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
C₃₉	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
C₃₈	Two-tier relaxed heaps more Amr Elmasry, Claus Jensen, and Jyrki Katajainen Acta Informatica 45,3 (2008), 193–210
C₃₇	Multipartite priority queues more Amr Elmasry, Claus Jensen, and Jyrki Katajainen ACM Transactions on Algorithms 5,1 (2008), Article 14, 19 pp.
C₃₆	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
C₃₅	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
C₃₄	Asymptotically efficient in-place merging more Viliam Geffert, Jyrki Katajainen, and Tomi A. Pasanen Theoretical Computer Science 237,1-2 (2000), 159–181
C₃₃	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.
C₃₂	In-place sorting with fewer moves more Jyrki Katajainen and Tomi A. Pasanen Information Processing Letters 70,1 (1999), 31–37
C₃₁	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
C₃₀	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
C₂₉	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
C₂₈	Practical in-place mergesort more Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola Nordic Journal of Computing 3,1 (1996), 27–40
C₂₇	Spørgsmål og svar om el-overfølsomhed more Margit Larsson and Jyrki Katajainen EBD Nyt 10 (1995)
C₂₆	Sorting multisets stably in minimum space more Jyrki Katajainen and Tomi A. Pasanen Acta Informatica 31,4 (1994), 301–313
C₂₅	Finding the maximum in parallel random access machines more Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Bulletin of the EATCS 52 (1994), 315–334
C₂₄	Space-efficient parallel merging more Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson RAIRO—Theoretical Informatics and Applications 27,4 (1993), 295–310
C₂₃	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
C₂₂	Stable minimum space partitioning in linear time more Jyrki Katajainen and Tomi A. Pasanen BIT 32,4 (1992), 580–585
C₂₁	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 I₁₅)
C₂₀	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
C₁₉	Maksimin määrääminen rinnakkaiskoneissa more Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Tietojenkäsittelytiede 2 (1991), 36–48 (A preliminary version of C₂₅)
C₁₈	A note on the complexity of trie compaction Jyrki Katajainen and Erkki Mäkinen Bulletin of the EATCS 41 (1990), 212–216
C₁₇	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
C₁₆	A sublogarithmic convex hull algorithm more Per-Olof Fjällström, Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson BIT 30,3 (1990), 378–384
C₁₅	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
C₁₄	An approximation algorithm for space-optimal encoding of a text more Jyrki Katajainen and Timo Raita The Computer Journal 32,3 (1989), 228–237
C₁₃	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
C₁₂	Constructing Delaunay triangulations by merging buckets in quadtree order more Jyrki Katajainen and Markku Koppinen Fundamenta Informaticae XI,3 (1988), 275–288
C₁₁	The region approach for computing relative neighbourhood graphs in the L_p metric more Jyrki Katajainen Computing 40,2 (1988), 147–161
C₁₀	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
C₉	An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics more Jyrki Katajainen and Olli Nevalainen Informatique Théorique et Applications 21,2 (1987), 199–215
C₈	Syntax-directed compression of program files more Jyrki Katajainen, Martti Penttonen, and Jukka Teuhola Software: Practice and Experience 16,3 (1986), 269–276
C₇	Computing relative neighbourhood graphs in the plane more Jyrki Katajainen and Olli Nevalainen Pattern Recognition 19,3 (1986), 221–228
C₆	Notes on the complexity of sorting in abstract machines more Martti Penttonen and Jyrki Katajainen BIT 25,4 (1985), 611–622
C₅	NP-completeness of the Hamming salesman problem more Jarmo Ernvall, Jyrki Katajainen, and Martti Penttonen BIT 25,1 (1985), 289–292
C₄	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
C₃	On the worst case of a minimal spanning tree algorithm for Euclidean space more Jyrki Katajainen BIT 23,1 (1983), 2–8
C₂	Experiments with a closest point algorithm in Hamming space more Olli Nevalainen and Jyrki Katajainen Angewandte Informatik 24,5 (1982), 277–281
C₁	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

D₅₈	Hacker’s multiple-precision integer-division program in close scrutiny more Jyrki Katajainen Proceedings of the 18th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 11544, Springer (2019), 376–391
D₅₇	A faster convex-hull algorithm via bucketing more Ask Neve Gamby and Jyrki Katajainen Proceedings of the 18th International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 11544, Springer (2019), 473–489
D₅₆	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
D₅₅	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
D₅₄	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
D₅₃	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
D₅₂	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
D₅₁	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)
D₅₀	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
D₄₉	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
D₄₈	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
D₄₇	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
D₄₆	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
D₄₅	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
D₄₄	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
D₄₃	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 C₄₂)
D₄₂	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
D₄₁	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 C₄₂)
D₄₀	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
D₃₉	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 C₄₃)
D₃₈	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
D₃₇	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
D₃₆	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
D₃₅	Stronger guarantees for standard-library containers more Jyrki Katajainen Oberwolfach Reports, 4,2, Mathematisches Forchungsinstitut Oberwolfach (2007), 1407–1411
D₃₄	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
D₃₃	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 C₄₀)
D₃₂	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
D₃₁	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 C₃₈)
D₃₀	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
D₂₉	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
D₂₈	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 C₃₆)
D₂₇	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
D₂₆	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
D₂₅	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 C₃₃)
D₂₄	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
D₂₃	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
D₂₂	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
D₂₁	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 C₃₁)
D₂₀	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
D₁₉	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
D₁₈	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
D₁₇	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
D₁₆	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
D₁₅	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 C₃₄)
D₁₄	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
D₁₃	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 C₃₀)
D₁₂	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 C₂₈)
D₁₁	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
D₁₀	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
D₉	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
D₈	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 C₂₆)
D₇	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 C₂₄)
D₆	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
D₅	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
D₄	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
D₃	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 C₁₄ and C₂₃)
D₂	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 C₈)
D₁	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 C₆)

E. Book parts

E₂	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
E₁	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 D₂₆)

F. Conference abstracts

F₆	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
F₅	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
F₄	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
F₃	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
F₂	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
F₁	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

G₁₂	Heap construction—50 years later more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Web document (2020)
G₁₁	A faster convex-hull algorithm via bucketing: Errata more Ask Neve Gamby and Jyrki Katajainen Web document (2019)
G₁₀	Performance engineering case study: Heap construction — Errata more Jesper Bojesen, Jyrki Katajainen, and Maz Spork Web document (2017)
G₉	Stable minimum space partitioning in linear time: Errata more Jyrki Katajainen and Tomi A. Pasanen Web document (2014)
G₈	Branch mispredictions don’t affect mergesort: Errata more Amr Elmasry, Jyrki Katajainen, and Max Stenmark Web document (2014)
G₇	Selection from read-only memory with limited workspace: Errata more Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, and Srinivasa Rao Satti Web document (2014)
G₆	Navigation piles with applications to sorting, priority queues, and priority deques: Errata more Jyrki Katajainen and Fabio Vitale Web document (2013)
G₅	The weak-heap family of priority queues in theory and praxis: Errata more Jyrki Katajainen Web document (2012)
G₄	Fat heaps without regular counters: Errata more Jyrki Katajainen Web document (2012)
G₃	Two constant-factor-optimal realizations of adaptive heapsort: Errata more Jyrki Katajainen Web document (2012)
G₂	Two-tier relaxed heaps: Errata more Jyrki Katajainen Web document (2012)
G₁	The weak-heap data structure: Variants and applications: Errata more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Web document (2012)

H. Edited publications

H₁₆	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
H₁₅	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.
H₁₄	Essays on C++ concepts more Jyrki Katajainen (Editor) CPH STL report 2008-4, Department of Computer Science, University of Copenhagen (2008), 14 pp.
H₁₃	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.
H₁₂	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.
H₁₁	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
H₁₀	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.
H₉	Project performance engineering: Final report more Jyrki Katajainen (Editor) CPH STL report 2002-5, Department of Computer Science, University of Copenhagen (2002), 11 pp.
H₈	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.
H₇	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.
H₆	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.
H₅	Proceedings of the 2nd Copenhagen Conference on Electromagnetic Hypersensitivity more Jyrki Katajainen and Bengt Knave (Editors) Danish Association for the Electromagnetically Hypersensitive (1995)
H₄	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
H₃	Adaptiivisia lajittelualgoritmeja C++ kielellä Jyrki Katajainen (Editor) Lecture Notes C10, Department of Computer Science, University of Turku (1990)
H₂	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.
H₁	Systemoinnin seminaariesitelmät Jyrki Katajainen and Markku Nurminen (Editors) Lecture Notes C4, Department of Computer Science, University of Turku (1984)

I. Technical reports

I₄₅	Writing C++ metafunctions procedurally more Jyrki Katajainen CPH STL report 2020-2, Department of Computer Science, University of Copenhagen (2020), 22 pp.
I₄₄	Pure compile-time functions and classes in the CPH MPL more Jyrki Katajainen CPH STL report 2017-2, Department of Computer Science, University of Copenhagen (2017), 54 pp.
I₄₃	A note on the implementation quality of a convex-hull algorithm more Ask Neve Gamby and Jyrki Katajainen CPH STL report 2017-3, Department of Computer Science, University of Copenhagen (2017), 25 pp.
I₄₂	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.
I₄₁	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.
I₄₀	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 C₄₆)
I₃₉	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.
I₃₈	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.
I₃₇	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.
I₃₆	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.
I₃₅	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.
I₃₄	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.
I₃₃	Mini-project: Safe standard-library containers more Jyrki Katajainen CPH STL report 2008-2, Department of Computer Science, University of Copenhagen (2008), 6 pp.
I₃₂	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.
I₃₁	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.
I₃₀	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.
I₂₉	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.
I₂₈	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.
I₂₇	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.
I₂₆	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.
I₂₅	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.
I₂₄	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.
I₂₃	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.
I₂₂	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.
I₂₁	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–2018), 7 pp.
I₂₀	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.
I₁₉	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 D₂₃)
I₁₈	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)
I₁₇	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.
I₁₆	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.
I₁₅	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.
I₁₄	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.
I₁₃	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.
I₁₂	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 C₂₂)
I₁₁	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 F₁)
I₁₀	Rinnakkaisalgoritmit (Luvut 1-4) Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Lecture Notes C9, Department of Computer Science, University of Turku (1990), 77 pp.
I₉	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.
I₈	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 D₃)
I₇	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 C₂₀)
I₆	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.
I₅	On the relationship between minimum matchings and Delaunay graphs in the L_p-metric Jyrki Katajainen Report A42, Department of Computer Science, University of Turku (1985), 10 pp.
I₄	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.
I₃	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 C₃)
I₂	Simulointi Jyrki Katajainen Lecture Notes, Department of Computer Science, University of Turku (1982), 81 pp.
I₁	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 C₁)

J. Computer programs

J₂₀	Documenting the CPH MPL—release 2—by code more Jyrki Katajainen CPH STL report 2020-1, Department of Computer Science, University of Copenhagen (2020), 109 pp.
J₁₉	Algorithm quickerhull in code more Jyrki Katajainen CPH STL report 2019-1, Department of Computer Science, University of Copenhagen (2019), 90 pp.
J₁₈	Convex-hull algorithms in C++ more Ask Neve Gamby and Jyrki Katajainen CPH STL report 2018-1, Department of Computer Science, University of Copenhagen (2018–2020), 107 pp.
J₁₇	Dynamic-array kernels more Jyrki Katajainen CPH STL report 2016-2, Department of Computer Science, University of Copenhagen (2016), 100 pp.
J₁₆	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.
J₁₅	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.
J₁₄	Sorting programs executing fewer branches more Jyrki Katajainen CPH STL report 2014-1, Department of Computer Science, University of Copenhagen (2014), 51 pp.
J₁₃	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.
J₁₂	Branchless search programs: Electronic appendix more Jyrki Katajainen CPH STL report 2012-1, Department of Computer Science, University of Copenhagen (2012–2013), 30 pp.
J₁₁	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.
J₁₀	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.
J₉	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.
J₈	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.
J₇	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.
J₆	Priority-queue frameworks: Programs more Jyrki Katajainen CPH STL report 2009-7, Department of Computer Science, University of Copenhagen (2009), ii+118 pp.
J₅	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 D₂₇)
J₄	Sorting & Searching Experimentarium more Svante Carlsson, Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola Web document (1997)
J₃	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.
J₂	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.
J₁	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 2020-05-23.