Jyrki Katajainen

Research output

Research output per year 1980 1994 1995 1997 1999 2000 2002 2006 2012 2013 2018

• 41 Working paper
• 38 Article in proceedings
• 32 Journal article
• 23 Report
• 40 More
  • 14 Book chapter
  • 10 Book
  • 6 Conference abstract in proceedings
  • 3 Conference article
  • 2 Report chapter
  • 2 Preface/postscript
  • 1 Anthology
  • 1 Paper
  • 1 Editorial

Research output per year

Research output per year

Search results

• 2018

  Computing convex hulls in the plane: Collected algorithms in C++

  Gamby, A. N. & Katajainen, J., 2018, Department of Computer Science, University of Copenhagen. 87 p. (CPH STL Report; No. 2018-1).

  Research output: Book/Report › Report › Research

• Convex-hull algorithms: Implementation, testing, and experimentation

  Gamby, A. N. & Katajainen, J., 2018, In: Algorithms. 11, 12, p. 1-27 195.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Experimentation 100%
  • Convex Hull 81%
  • Testing 59%
  • Experimental Results 55%
  • Plane Sweep 46%
  8 Citations (Scopus)

  59 Downloads (Pure)
• 2017

  All-in-one implementation framework for binary heaps

  Katajainen, J., 1 Apr 2017, In: Software: Practice and Experience. 47, 4, p. 523-558 36 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Textbooks 100%
  • Data structures 66%

• A note on the implementation quality of a convex-hull algorithm

  Gamby, A. N. & Katajainen, J., 2017, Department of Computer Science, University of Copenhagen. 25 p. (CPH STL Report; No. 2017-3).

  Research output: Book/Report › Report › Research

• Bipartite binomial heaps

  Elmasry, A., Jensen, C. & Katajainen, J., Jul 2017, In: RAIRO - Theoretical Informatics and Applications. 51, 3, p. 121-133 13 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Heap 100%
  • Data structures 60%
  • Data Structures 55%
  • Costs 39%
  • Union 14%

• Heap Construction—50 Years Later

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 1 Apr 2017, In: The Computer Journal. 60, 5, p. 657-674 18 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Tuning 100%
  1 Citation (Scopus)

• Optimizing binary heaps

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., Aug 2017, In: Theory of Computing Systems. 61, 2, p. 606-636 31 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  3 Citations (Scopus)

• Pure compile-time functions and classes in the CPH MPL

  Katajainen, J., 2017, Department of Computer Science, University of Copenhagen. 54 p. (CPH STL Report; No. 2017-2).

  Research output: Book/Report › Report › Research
• 2016

  Dynamic-array kernels

  Katajainen, J., 28 Mar 2016, Department of Computer Science, University of Copenhagen. 100 p. (CPH STL Report; No. 2, Vol. 2016).

  Research output: Book/Report › Report › Research

  21 Downloads (Pure)

• Editorial, SEA 2014 Special Issue

  Gudmundsson, J. & Katajainen, J., 5 Apr 2016, In: Journal of Experimental Algorithmics. 21, 1 p., 1.1.

  Research output: Contribution to journal › Editorial

• Heap-construction programs

  Edelkamp, S., Elmasry, A. & Katajainen, J., 4 Nov 2016, Department of Computer Science, University of Copenhagen. 54 p. (CPH STL Report; No. 2, Vol. 2016).

  Research output: Book/Report › Report › Research

  24 Downloads (Pure)

• Worst-case-efficient dynamic arrays in practice

  Katajainen, J., 2016, Experimental Algorithms: 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings. Goldberg, A. V. & Kulikov, A. S. (eds.). Springer, p. 167-183 17 p. (Lecture notes in computer science, Vol. 9685).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Libraries 100%
  • Slice 98%
  • Costs 66%
  • Worst-case Performance 63%
  • Slicing 61%
  2 Citations (Scopus)
• 2015

  All-in-one implementation framework for binary heaps

  Katajainen, J., 2015, Department of Computer Science, University of Copenhagen. 50 p. (CPH STL Report; No. 2015-1).

  Research output: Book/Report › Report › Research

• All-in-one implementation framework for binary heaps: electronic appendix

  Katajainen, J., 2015, Department of Computer Science, University of Copenhagen. 111 p. (CPH STL Report; No. 2015-2).

  Research output: Book/Report › Report › Research

• An in-place priority queue with O(1) Time for Push and lg n + O(1) comparisons for pop

  Edelkamp, S., Elmasry, A. & Katajainen, J., 2015, Computer science - theory and applications: 10th International Computer Science Symposium in Russia, CSR 2015, Listvyanka, Russia, July 13-17, 2015, Proceedings. Beklemishev, L. D. & Musatov, D. V. (eds.). Springer, p. 204-218 15 p. (Lecture notes in computer science, Vol. 9139).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  1 Citation (Scopus)
• 2014

  Experimental Algorithms: 13th International Symposium, SEA 2014, Copenhagen, Denmark, Proceedings

  Gudmundsson, J. (ed.) & Katajainen, J. (ed.), 2014, Springer. 466 p. (Lecture notes in computer science, Vol. 8504).

  Research output: Book/Report › Book › Research › peer-review

• Selection from read-only memory with limited workspace

  Elmasry, A., Juhl, D. D., Katajainen, J. & Satti, S. R., 2014, In: Theoretical Computer Science. 554, p. 64-73 10 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Workspace 100%
  • ROM 87%
  • Random Access 32%
  • Wavelets 20%
  • Streaming 15%
  7 Citations (Scopus)

• Sorting programs executing fewer branches

  Katajainen, J., 2014, Department of Computer Science, University of Copenhagen. 37 p. (CPH STL Report, Vol. 2014-1).

  Research output: Book/Report › Report › Research › peer-review

• Strengthened lazy heaps: surpassing the lower bounds for binary heaps

  Edelkamp, S., Elmasry, A. & Katajainen, J., 2014, In: arXiv.org: Computer science. arXiv:1407.3377, 14 p.

  Research output: Contribution to journal › Journal article › Research
• 2013

  Branchless search programs

  Elmasry, A. & Katajainen, J., 2013, Experimental Algorithms: 12th International Symposium, SEA 2013, Rome, Italy, June 5-7, 2013. Proceedings. Bonifaci, V., Demetrescu, C. & Marchetti-Spaccamela, A. (eds.). Springer, p. 127-138 12 p. (Lecture notes in computer science, Vol. 7933).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Microscopic examination 100%
  2 Citations (Scopus)

• Conceptual frameworks for constructing iterators for compound data structures - Electronic appendix I: component-iterator and rank-iterator classes

  Katajainen, J. & Maniotis, A. M., 2013, Department of Computer Science, University of Copenhagen. 47 p. (CPH STL Report; No. 2012-3).

  Research output: Book/Report › Report › Research

• Fat heaps without regular counters

  Elmasry, A. & Katajainen, J., 1 Jun 2013, In: Discrete Mathematics, Algorithms and Applications. 5, 21 p., 1360006.

  Research output: Contribution to journal › Conference article › Research › peer-review

  • Heap 100%
  • Experimental Results 24%
  • Decrease 21%
  1 Citation (Scopus)

• In-place binary counters

  Elmasry, A. A. A. E. & Katajainen, J., 2013, Mathematical Foundations of Computer Science 2013: 38th International Symposium, MFCS 2013, Klosterneuburg, Austria, August 26-30, 2013. Proceedings. Chatterjee, K. & Sgall, J. (eds.). Springer, p. 349-360 12 p. (Lecture notes in computer science).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Binary codes 100%
  • Data structures 66%
  1 Citation (Scopus)

• Priority queues and sorting for read-only data

  Asano, T., Elmasry, A. & Katajainen, J., 2013, Theory and Applications of Models of Computation: 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22, 2013. Proceedings. Chan, T-H. H., Lau, L. C. & Trevisan, L. (eds.). Springer, p. 32-41 10 p. (Lecture notes in computer science, Vol. 7876).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Sorting 100%
  • Piles 32%
  • Data structures 28%
  • Navigation 26%
  16 Citations (Scopus)

  91 Downloads (Pure)

• Seeking for the best priority queue: lessons learnt

  Katajainen, J., 2013, Department of Computer Science, University of Copenhagen. 10 p. (CPH STL Report, Vol. 2013-3).

  Research output: Book/Report › Report › Research

• Selection from read-only memory with limited workspace

  Elmasry, A., Juhl, D. D., Katajainen, J. & Satti, S. R., 2013, Computing and Combinatorics: 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings. Du, D-Z. & Zhang, G. (eds.). Springer, p. 147-157 11 p. (Lecture notes in computer science, Vol. 7936).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • ROM 100%
  • Textbooks 16%
  7 Citations (Scopus)

• Towards ultimate binary heaps

  Elmasry, A. & Katajainen, J., 2013, Department of Computer Science, University of Copenhagen. 13 p. (CPH STL Report, Vol. 2013-1).

  Research output: Book/Report › Report › Research

• Weak heaps and friends: recent developments

  Edelkamp, S., Elmasry, A., Katajainen, J. & Weiß, A., 2013, Combinatorial Algorithms: 24th International Workshop, IWOCA 2013, Rouen, France, July 10-12, 2013, Revised Selected Papers. Lecroq, T. & Mouchard, L. (eds.). Springer, p. 1-6 6 p. (Lecture notes in computer science, Vol. 8288).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Heap 100%
  • Data Structures 20%
  • Sorting algorithm 19%
  • Sorting 15%
  • Graph Search 10%
  90 Downloads (Pure)

• Weak heaps engineered

  Edelkamp, S., Elmasry, A. & Katajainen, J., Nov 2013, In: Journal of Discrete Algorithms. 23, p. 83-97 15 p.

  Research output: Contribution to journal › Conference article › Research › peer-review

  • Heap 100%
  • Cache 30%
  • Priority Queue 29%
  • Branch 27%
  • Insertion 23%
  4 Citations (Scopus)
• 2012

  A catalogue of algorithms for building weak heaps

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 2012, Combinatorial Algorithms: 23rd International Workshop, IWOCA 2012, Tamil Nadu, India, July 19-21, 2012, Revised Selected Papers. Arumugam, S. & Smyth, W. F. (eds.). Springer, p. 249-262 14 p. (Lecture notes in computer science, Vol. 7643).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Heap 100%
  • Cache 27%
  • Priority Queue 26%
  • Layout 21%
  • Insertion 20%
  2 Citations (Scopus)

• A catalogue of weak-heap programs

  Edelkamp, S., Elmasry, A. & Katajainen, J., 2012, Department of Computer Science, University of Copenhagen. 36 p. (CPH STL Report; No. 2012-2).

  Research output: Book/Report › Report › Research

• Adaptive heapsort: source code

  Edelkamp, S., Elmasry, A. & Katajainen, J., 2012, Department of Computer Science, University of Copenhagen. 29 p. (CPH STL Report; No. 2011-1).

  Research output: Book/Report › Report › Research

• Branch mispredictions don’t affect mergesort

  Elmasry, A. A. A. E., Katajainen, J. & Stenmark, M., 2012, Experimental Algorithms: 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings. Klasing, R. (ed.). Springer, p. 160-171 12 p. (Lecture notes in computer science, Vol. 7276).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Quicksort 100%
  • Branch 96%
  • Sorting 76%
  • Pivot 54%
  • Decoupling 50%
  9 Citations (Scopus)

• Fat heaps without regular counters

  Elmasry, A. A. A. E. & Katajainen, J., 2012, WALCOM: Algorithms and Computation: 6th International Workshop, WALCOM 2012, Dhaka, Bangladesh, February 15-17, 2012. Proceedings. Rahman, M. S. & Nakano, S. (eds.). Springer, p. 173-185 13 p. (Lecture notes in computer science, Vol. 7157).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Oils and fats 100%
  3 Citations (Scopus)

• Improved address-calculation coding of integer arrays

  Elmasry, A. A. A. E., Katajainen, J. & Teuhola, J., 2012, String Processing and Information Retrieval: 19th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, October 21-25, 2012. Proceedings. Calderón-Benavides, L., González-Caro, C., Chávez, E. & Ziviani, N. (eds.). Springer, p. 205-216 12 p. (Lecture notes in computer science, Vol. 7608).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Random access storage 100%
  • Data structures 75%
  • Data storage equipment 55%
  • Experiments 32%
  3 Citations (Scopus)

• In-place heap construction with optimized comparisons, moves, and cache misses

  Chen, J., Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 2012, Mathematical Foundations of Computer Science 2012: 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings. Rovan, B., Sassone, V. & Widmayer, P. (eds.). Springer, p. 259-270 12 p. (Lecture notes in computer science, Vol. 7464).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Piles 100%
  • Navigation 79%
  6 Citations (Scopus)

• Lean programs, branch mispredictions, and sorting

  Elmasry, A. A. A. E. & Katajainen, J., 2012, Fun with Algorithms: 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings. Kranakis, E., Krizanc, D. & Luccio, F. (eds.). Springer, p. 119-130 12 p. (Lecture notes in computer science, Vol. 7288).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • sorting 100%
  • hands 42%
  • prediction 33%
  6 Citations (Scopus)

• The Open Graph Archive: a community-driven effort

  Bachmaier, C., Brandenburg, F. J., Effinger, P., Gutwenger, C., Katajainen, J., Klein, K., Spönemann, M., Stegmaier, M. & Wybrow, M., 2012, Graph Drawing: 19th International Symposium, GD 2011, Eindhoven, The Netherlands, September 21-23, 2011, Revised Selected Papers. Kreveld, M. & Speckmann, B. (eds.). Springer, p. 435-440 6 p. (Lecture notes in computer science, Vol. 7034).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Computer program listings 100%
  4 Citations (Scopus)

• The weak-heap data structure: variants and applications

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., Oct 2012, In: Journal of Discrete Algorithms. 16, p. 187-205 19 p.

  Research output: Contribution to journal › Conference article › Research › peer-review

  • Heap 100%
  • Data Structures 74%
  • Priority Queue 59%
  • Buffer 24%
  • Decrease 18%
  9 Citations (Scopus)

• The weak-heap family of priority queues in theory and praxis

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 2012, Proceedings of the Eighteenth Computing: The Australasian Theory Symposium. Mestre, J. (ed.). Australian Computer Society, p. 103-112 10 p. (Conferences in Research and Practice in Information Technology, Vol. 128).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Priority Queue 100%
  • Heap 95%
  • Family 32%
  • Queue 22%
  • Experimental Results 11%
  6 Citations (Scopus)

  12 Downloads (Pure)

• Two skew-binary numeral systems and one application

  Elmasry, A. A. A. E., Jensen, C. & Katajainen, J., Jan 2012, In: Theory of Computing Systems. 50, 1, p. 185-211 27 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Numeral 100%
  • Skew 62%
  • Binary 51%
  • Priority Queue 27%
  • Digit 20%
  3 Citations (Scopus)

• Weak-heap and weak-queue frameworks: source code

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 2012, Department of Computer Science, University of Copenhagen. 81 p. (CPH STL Report; No. 2011-2).

  Research output: Book/Report › Report › Research

• Worst-case optimal priority queues via extended regular counters

  Elmasry, A. A. A. E. & Katajainen, J., 2012, Computer Science – Theory and Applications : 7th International Computer Science Symposium in Russia, CSR 2012, Nizhny Novgorod, Russia, July 3-7, 2012. Proceedings. Hirsch, E. A., Karhumäki, J., Lepistö, A. & Prilutskii, M. (eds.). Springer, p. 125-137 13 p. (Lecture notes in computer science, Vol. 7353).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Priority Queue 100%
  • Data Structures 28%
  • Time Constant 16%
  • Decrease 12%
  • Logarithmic 11%
  5 Citations (Scopus)
• 2011

  Fat heaps: source code

  Elmasry, A. A. A. E. & Katajainen, J., 2011, Department of Computer Science, University of Copenhagen. 54 p. (CPH STL Report, Vol. 2010-2).

  Research output: Book/Report › Report › Research

• Graph archive

  Bachmaier, C., Brandenburg, F. J., Effinger, P., Gutwenger, C., Katajainen, J., Klein, K., Spönemann, M. & Wybrow, M., 2011, Graph drawing with algorithm engineering methods (Dagstuhl Seminar 11191): report from Dagstuhl Seminar 11191. Demetrescu, C., Kaufmann, M., Kobourov, S. & Mutzel, P. (eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, p. 52-53 2 p.

  Research output: Chapter in Book/Report/Conference proceeding › Conference abstract in proceedings › Research › peer-review

  42 Downloads (Pure)

• Two constant-factor-optimal realizations of adaptive heapsort

  Edelkamp, S., Elmasry, A. A. A. E. & Katajainen, J., 2011, Combinatorial Algorithms: 22nd International Workshop, IWOCA 2011, Victoria, BC, Canada, July 20-22, 2011, Revised Selected Papers. Iliopoulos, C. S. & Smyth, W. F. (eds.). Springer, p. 195-208 14 p. (Lecture notes in computer science, Vol. 7056).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Priority Queue 100%
  • Queue 34%
  • Sorting algorithm 25%
  • Heap 23%
  • Adaptive Algorithm 20%
  2 Citations (Scopus)
• 2010

  A compact data structure for representing a dynamic multiset

  Katajainen, J. & Rao, S. S., 2010, In: Information Processing Letters. 110, 23, p. 1061-1066 6 p.

  Research output: Contribution to journal › Journal article › Research › peer-review

  • Multiset 100%
  • Data Structures 90%
  • Data structures 72%
  • Update 57%
  • Requirements 23%
  1 Citation (Scopus)

• Policy-based benchmarking of weak heaps and their relatives

  Bruun, A., Edelkamp, S., Katajainen, J. & Rasmussen, J., 2010, Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20-22, 2010. Proceedings. Festa, P. (ed.). Springer, p. 424-435 12 p. (Lecture notes in computer science, Vol. 6049).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Binary trees 100%
  • Benchmarking 84%
  12 Citations (Scopus)

• Strictly-regular number system and data structures

  Elmasry, A. A. A. E., Jensen, C. & Katajainen, J., 2010, Algorithm Theory - SWAT 2010: 12th Scandinavian Symposium and Workshops on Algorithm Theory, Bergen, Norway, June 21-23, 2010. Proceedings. Kaplan, H. (ed.). Springer, p. 26-37 12 p. (Lecture notes in computer science, Vol. 6139).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Data structures 100%
  5 Citations (Scopus)

• The magic of a number system

  Elmasry, A. A. A. E., Jensen, C. & Katajainen, J., 2010, Fun with Algorithms: 5th International Conference, FUN 2010, Ischia, Italy, June 2-4, 2010. Proceedings. Boldi, P. & Gargano, L. (eds.). Springer, p. 156-165 10 p. (Lecture notes in computer science, Vol. 6099).

  Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

  • Binary trees 100%
  • Data structures 66%
  • Costs 61%
  1 Citation (Scopus)