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