Jyrki Katajainen: Publications

2020

•	Writing C++ metafunctions procedurally more Jyrki Katajainen CPH STL report 2020-2, Department of Computer Science, University of Copenhagen (2020), 22 pp.
•	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.

2019

•	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
•	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
•	Algorithm quickerhull in code more Jyrki Katajainen CPH STL report 2019-1, Department of Computer Science, University of Copenhagen (2019), 90 pp.

2018

•	Convex-hull algorithms: Implementation, testing, and experimentation more Ask Neve Gamby and Jyrki Katajainen Algorithms 11,12 (2018), Article 195
•	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.

2017

•	All-in-one implementation framework for binary heaps more Jyrki Katajainen Software: Practice and Experience 47,4 (2017), 523–558
•	Bipartite binomial heaps more Amr Elmasry, Claus Jensen, and Jyrki Katajainen RAIRO—Theoretical Informatics and Applications 51,3 (2017), 121–133
•	Heap construction—50 years later more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen The Computer Journal 60,5 (2017), 657–674
•	Optimizing binary heaps more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Theory of Computing Systems 61,2 (2017), 606–636
•	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.
•	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.

2016

•	Editorial, SEA 2014 Special Issue more Joachim Gudmundsson and Jyrki Katajainen ACM Journal of Experimental Algorithmics 21 (2016), Article 1.1, 1 p.
•	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
•	Dynamic-array kernels more Jyrki Katajainen CPH STL report 2016-2, Department of Computer Science, University of Copenhagen (2016), 100 pp.
•	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.

2015

•	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
•	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.
•	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.
•	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.

2014

•	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
•	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
•	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
•	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 [Elmasry, Juhl, Katajainen, and Satti 2014])
•	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.
•	Sorting programs executing fewer branches more Jyrki Katajainen CPH STL report 2014-1, Department of Computer Science, University of Copenhagen (2014), 51 pp.

2013

•	Fat heaps without regular counters more Amr Elmasry and Jyrki Katajainen Discrete Mathematics, Algorithms and Applications 5,2 (2013), Article 1360006, 21 pp.
•	Weak heaps engineered more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Journal of Discrete Algorithms 23 (2013), 83–97
•	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
•	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
•	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
•	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)
•	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
•	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.
•	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.

2012

•	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
•	The weak-heap data structure: Variants and applications more Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen Journal of Discrete Algorithms 16 (2012), 187–205
•	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
•	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
•	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
•	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
•	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
•	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
•	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 [Edelkamp, Elmasry, and Katajainen 2012])
•	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
•	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.
•	Branchless search programs: Electronic appendix more Jyrki Katajainen CPH STL report 2012-1, Department of Computer Science, University of Copenhagen (2012–2013), 30 pp.
•	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.

2011

•	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 [Edelkamp, Elmasry, and Katajainen 2012])
•	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
•	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
•	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.
•	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.
•	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.
•	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.

2010

•	A compact data structure for representing a dynamic multiset more Jyrki Katajainen and Srinivasa Rao Satti Information Processing Letters 110,23 (2010), 1061–1066
•	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 [Elmasry, Jensen, and Katajainen 2012])
•	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
•	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
•	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.
•	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.

2009

•	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
•	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
•	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
•	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.
•	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.
•	Priority-queue frameworks: Programs more Jyrki Katajainen CPH STL report 2009-7, Department of Computer Science, University of Copenhagen (2009), ii+118 pp.

2008

•	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
•	Two-tier relaxed heaps more Amr Elmasry, Claus Jensen, and Jyrki Katajainen Acta Informatica 45,3 (2008), 193–210
•	Multipartite priority queues more Amr Elmasry, Claus Jensen, and Jyrki Katajainen ACM Transactions on Algorithms 5,1 (2008), Article 14, 19 pp.
•	Essays on C++ concepts more Jyrki Katajainen (Editor) CPH STL report 2008-4, Department of Computer Science, University of Copenhagen (2008), 14 pp.
•	Mini-project: Safe standard-library containers more Jyrki Katajainen CPH STL report 2008-2, Department of Computer Science, University of Copenhagen (2008), 6 pp.
•	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.

2007

•	Stronger guarantees for standard-library containers more Jyrki Katajainen Oberwolfach Reports, 4,2, Mathematisches Forchungsinstitut Oberwolfach (2007), 1407–1411
•	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
•	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 [Gudmundsson, Katajainen, Merrick, Ong, and Wolle 2009])
•	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
•	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.
•	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.

2006

•	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.
•	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 [Elmasry, Jensen, and Katajainen 2008])
•	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
•	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.
•	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.
•	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.
•	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.
•	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.
•	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.

2005

•	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.
•	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.
•	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.

2004

•	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
•	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

2003

•	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
•	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.

2002

•	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
•	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
•	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 [Brönnimann, Iacono, Katajainen, Morin, Morrison, and Toussaint 2004])
•	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.
•	Project performance engineering: Final report more Jyrki Katajainen (Editor) CPH STL report 2002-5, Department of Computer Science, University of Copenhagen (2002), 11 pp.

2001

•	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
•	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
•	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.
•	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.
•	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 [Katajainen and Mortensen 2001])

2000

•	Asymptotically efficient in-place merging more Viliam Geffert, Jyrki Katajainen, and Tomi A. Pasanen Theoretical Computer Science 237,1-2 (2000), 159–181
•	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.
•	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 [Bojesen and Katajainen 2001])
•	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.
•	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.

1999

•	In-place sorting with fewer moves more Jyrki Katajainen and Tomi A. Pasanen Information Processing Letters 70,1 (1999), 31–37
•	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
•	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 [Bojesen, Katajainen, and Spork 2000])

1998

•	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
•	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
•	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

1997

•	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
•	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
•	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 [Fadel, Jakobsen, Katajainen, and Teuhola 1999])
•	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
•	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
•	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.
•	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 [Brodal and Katajainen 1998])
•	Sorting & Searching Experimentarium more Svante Carlsson, Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola Web document (1997)

1996

•	Practical in-place mergesort more Jyrki Katajainen, Tomi A. Pasanen, and Jukka Teuhola Nordic Journal of Computing 3,1 (1996), 27–40
•	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
•	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
•	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)

1995

•	Spørgsmål og svar om el-overfølsomhed more Margit Larsson and Jyrki Katajainen EBD Nyt 10 (1995)
•	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
•	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
•	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
•	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 [Geffert, Katajainen, and Pasanen 2000])
•	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
•	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 [Hagerup, Katajainen, Nishimura, and Ragde 1998])
•	Proceedings of the 2nd Copenhagen Conference on Electromagnetic Hypersensitivity more Jyrki Katajainen and Bengt Knave (Editors) Danish Association for the Electromagnetically Hypersensitive (1995)
•	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.

1994

•	Sorting multisets stably in minimum space more Jyrki Katajainen and Tomi A. Pasanen Acta Informatica 31,4 (1994), 301–313
•	Finding the maximum in parallel random access machines more Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Bulletin of the EATCS 52 (1994), 315–334
•	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 [Katajainen, Pasanen, and Teuhola 1996])
•	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
•	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
•	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.
•	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.

1993

•	Space-efficient parallel merging more Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson RAIRO—Theoretical Informatics and Applications 27,4 (1993), 295–310
•	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
•	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
•	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.
•	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.

1992

•	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
•	Stable minimum space partitioning in linear time more Jyrki Katajainen and Tomi A. Pasanen BIT 32,4 (1992), 580–585
•	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 [Katajainen, Leppänen, and Penttonen 1994])
•	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 [Katajainen and Pasanen 1994])
•	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 [Katajainen, Levcopoulos, and Petersson 1993])
•	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
•	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 [Katajainen and Pasanen 1992])
•	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 [Fjällström, Katajainen, and Petersson 1991])

1991

•	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
•	Maksimin määrääminen rinnakkaiskoneissa more Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Tietojenkäsittelytiede 2 (1991), 36–48 (A preliminary version of [Auramo, Katajainen, and Kulmala 1994])
•	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

1990

•	A note on the complexity of trie compaction Jyrki Katajainen and Erkki Mäkinen Bulletin of the EATCS 41 (1990), 212–216
•	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
•	A sublogarithmic convex hull algorithm more Per-Olof Fjällström, Jyrki Katajainen, Christos Levcopoulos, and Ola Petersson BIT 30,3 (1990), 378–384
•	Adaptiivisia lajittelualgoritmeja C++ kielellä Jyrki Katajainen (Editor) Lecture Notes C10, Department of Computer Science, University of Turku (1990)
•	Rinnakkaisalgoritmit (Luvut 1-4) Yrjö Auramo, Jyrki Katajainen, and Juhani Kulmala Lecture Notes C9, Department of Computer Science, University of Turku (1990), 77 pp.

1989

•	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
•	An approximation algorithm for space-optimal encoding of a text more Jyrki Katajainen and Timo Raita The Computer Journal 32,3 (1989), 228–237
•	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

1988

•	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
•	Constructing Delaunay triangulations by merging buckets in quadtree order more Jyrki Katajainen and Markku Koppinen Fundamenta Informaticae XI,3 (1988), 275–288
•	The region approach for computing relative neighbourhood graphs in the L_p metric more Jyrki Katajainen Computing 40,2 (1988), 147–161
•	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
•	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.

1987

•	Bucketing and filtering in computational geometry more Jyrki Katajainen Ph.D. Thesis, Department of Computer Science, University of Turku (1987), vi+120 pp. (Includes [Katajainen 1983], [Katajainen and Nevalainen 1986], [Katajainen and Nevalainen 1987], [Katajainen, Nevalainen, and Teuhola 1987], [Katajainen 1988], [Katajainen and Koppinen 1988]; Public discussion November 1987)
•	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
•	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
•	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 [Katajainen and Raita 1989] and [Katajainen and Raita 1992])

1986

•	Syntax-directed compression of program files more Jyrki Katajainen, Martti Penttonen, and Jukka Teuhola Software: Practice and Experience 16,3 (1986), 269–276
•	Computing relative neighbourhood graphs in the plane more Jyrki Katajainen and Olli Nevalainen Pattern Recognition 19,3 (1986), 221–228
•	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 [Katajainen and Raita 1987])
•	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 [Juhola, Katajainen, and Raita 1991])

1985

•	Notes on the complexity of sorting in abstract machines more Martti Penttonen and Jyrki Katajainen BIT 25,4 (1985), 611–622
•	NP-completeness of the Hamming salesman problem more Jarmo Ernvall, Jyrki Katajainen, and Martti Penttonen BIT 25,1 (1985), 289–292
•	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 [Katajainen, Penttonen, and Teuhola 1986])
•	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.
•	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.
•	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.
•	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.

1984

•	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 [Penttonen and Katajainen 1985])
•	Systemoinnin seminaariesitelmät Jyrki Katajainen and Markku Nurminen (Editors) Lecture Notes C4, Department of Computer Science, University of Turku (1984)
•	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.

1983

•	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 [Ernvall, Katajainen, and Nevalainen 1980], [Katajainen 1981], [Katajainen 1982], [Nevalainen and Katajainen 1982], [Katajainen and Nevalainen 1983], [Katajainen 1983])
•	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
•	On the worst case of a minimal spanning tree algorithm for Euclidean space more Jyrki Katajainen BIT 23,1 (1983), 2–8
•	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.

1982

•	Experiments with a closest point algorithm in Hamming space more Olli Nevalainen and Jyrki Katajainen Angewandte Informatik 24,5 (1982), 277–281
•	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 [Katajainen 1983])
•	Simulointi Jyrki Katajainen Lecture Notes, Department of Computer Science, University of Turku (1982), 81 pp.

1981

•	Finding minimal spanning trees in a Euclidean coordinate space more Olli Nevalainen, Jarmo Ernvall, and Jyrki Katajainen BIT 21,1 (1981), 46–54
•	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.

1980

•	Tree automata and context-free languages (in Finnish) Jyrki Katajainen Master's Thesis, Department of Mathematics, University of Turku (1980), 58 pp.
•	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 [Nevalainen, Ernvall, and Katajainen 1981])

This page was generated by Jyrki Katajainen <jyrki@di.ku.dk> on 2020-05-23.