Publications of Riko Jacob

Riko Jacob at google scholar

The copyrights for journals and conference proceedings articles belong to the respective publisher.

Michael T. Goodrich, Riko Jacob and Nodari Sitchinava.
Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). DOI:10.1137/1.9781611976465.128
Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, and Stefan Langerman.
Fragile Complexity of Adaptive Algorithms.
Proceedings 12th International Conference, CIAC 2021. Springer, 2021. DOI:10.1007/978-3-030-75242-2_10
Mayank Goswami, Riko Jacob and Rasmus Pagh.
On the I/O Complexity of the k-Nearest Neighbors Problem.
PODS 20: Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems June 2020. DOI:10.1145/3375395.3387649 arXiv:2002.04870
Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck and Nodari Sitchinava.
Fragile Complexity of Comparison-Based Algorithms.
In Proceedings ESA 2019, LIPICS Vol. 144, Best paper award, Track A. DOI:10.4230/LIPIcs.ESA.2019.2 arXiv:1901.02857
John Iacono, Riko Jacob, Konstantinos Tsakalidis.
External memory priority queues with decrease-key and applications to graph algorithms.
In Proceedings ESA 2019, LIPICS Vol. 144. DOI:10.4230/LIPIcs.ESA.2019.60 arXiv:1903.03147
Gerth Brodal and Riko Jacob.
Dynamic Planar Convex Hull.
arXiv:1902.11169 . February 2019
Riko Jacob, Kasper Green Larsen and Jesper Buus Nielsen.
Lower Bounds for Oblivious Data Structures.
SODA 2019, the ACM-SIAM Symposium on Discrete Algorithms. DOI:10.1137/1.9781611975482.149 arXiv:1810.10635
Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Riko Jacob, and Stefan Schmid.
Charting the Algorithmic Complexity of Waypoint Routing.
ACM SIGCOMM Computer Communication Review (CCR), 2018. DOI:10.1145/3211852.3211859 CCR January 2018 arXiv:1705.00055
Matteo Dusefante and Riko Jacob.
Cache Oblivious Sparse Matrix Multiplication.
Proceedings of 13th Latin American Theoretical Informatics Symposium, LNCS 10807 pages 437-447. Springer-Verlag, 2018. DOI:10.1007/978-3-319-77404-6_32
Riko Jacob and Nodari Sitchinava.
Lower Bounds in the Asymmetric External Memory Model.
29th ACM Symposium on Parallelism in Algorithms and Architectures, Washington D.C., USA, July 24 - 26, 2017. DOI:10.1145/3087556.3087583 AEMspaa17.pdf (680K)
Philipp Hupp, Riko Jacob, Mario Heene and Dirk Pflüger.
Global communication schemes for the numerical solution of high-dimensional PDEs.
Parallel Computing (Elsevier), Volume 52, February 2016. DOI:10.1016/j.parco.2015.12.006
Riko Jacob, Morten Stöckel.
Fast Output-Sensitive Matrix Multiplication.
In Proceedings ESA 2015, LNCS 9294, pp. 766-778, 2015. DOI:10.1007/978-3-662-48350-3_64 JacobStoeckelFastMatrix.pdf (372K) © LNCS Springer-Verlag.
Philipp Hupp and Riko Jacob.
A Cache-Optimal Alternative to the Unidirectional Hierarchization Algorithm.
Sparse Grids and Applications - Stuttgart 2014, LNCSE vol 109, pages 103-132, Springer. DOI:10.1007/978-3-319-28262-6_5 paperSGA2014.pdf (496K).
Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig.
Skip+: A Self-Stabilizing Skip Graph.
Journal of the ACM, Volume 61 Issue 6, November 2014. DOI:10.1145/2629695
Riko Jacob, Tobias Lieber and Nodari Sitchinava.
On the Complexity of List Ranking in the Parallel External Memory Model.
Proceedings MFCS 2014, LNCS vol 8635, pages 384-395, Springer 2014. DOI:10.1007/978-3-662-44465-8_33 Full version: arXiv:1406.3279
Riko Jacob, Tobias Lieber and Matthias Mnich.
Treewidth Computation and Kernelization in the Parallel External Memory Model.
Proceedings TCS 2014, LNCS vol 8705, pages 78-89, Springer 2014. DOI:10.1007/978-3-662-44602-7_7
Jeremy Chalopin, Riko Jacob, Matus Mihalak and Peter Widmayer.
Data Delivery by Energy-Constrained Mobile Agents on a Line.
Proceedings ICALP 2014, LNCS vol 8573, pages 423-434, Springer 2014. DOI:10.1007/978-3-662-43951-7_36
Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig.
A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization.
Theory of Computing Systems, Volume 55, Issue 1, pp 110-135. DOI:10.1007/s00224-013-9504-x
Philipp Hupp, Riko Jacob, Mario Heene, Dirk Pflüger and Markus Hegland.
Global Communication Schemes for the Sparse Grid Combination Technique.
Parallel Computing: Accelerating Computational Science and Engineering (CSE), pages 564-573. DOI:10.3233/978-1-61499-381-0-564
Riko Jacob.
Efficient Regular Sparse Grid Hierarchization by a Dynamic Memory Layout.
Sparse Grids and Applications - Munich 2012, LNCSE vol 97, pages 195-219, Springer. DOI:10.1007/978-3-319-04537-5_8 SGAProceedings.pdf (508K).
Gerrit Buse, Dirk Pflüger and Riko Jacob.
Efficient Pseudorecursive Evaluation Schemes for Non-adaptive Sparse Grids.
Sparse Grids and Applications - Munich 2012, LNCSE vol 97, pages 1-27, Springer. DOI:10.1007/978-3-319-04537-5_1
Philipp Hupp and Riko Jacob.
Tight Bounds for Low Dimensional Star Stencils in the External Memory Model.
Algorithms and Data Structures Symposium, WADS 2013, London, Canada, August 12-14, 2013. Proceedings, LNCS 8037, pages 415-426. Springer-Verlag, 2013. DOI:10.1007/978-3-642-40104-6_36 Full version: arXiv:1205.0606
Gerrit Buse, Dirk Pflüger, Alin Florindor Murarasu and Riko Jacob.
Non-static Data Layout Enhancing Parallelism and Vectorization in Sparse Grid Algorithms.
11th International Symposium on Parallel and Distributed Computing, ISPDC 2012, Munich, Germany, June 25-29, 2012. Proceedings, pages 195-202. IEEE Computer Society, 2012. DOI:10.1109/ISPDC.2012.34 EE
Gero Greiner and Riko Jacob.
The Efficiency of MapReduce in Parallel External Memory.
Proceedings of 10th Latin American Theoretical Informatics Symposium, LNCS 7256 pages 433-445. Springer-Verlag, 2012. DOI:10.1007/978-3-642-29344-3_37 arXiv:1112.3765
Riko Jacob, Stephan Ritscher, Christian Scheideler, and Stefan Schmid.
Towards higher-dimensional topological self-stabilization: A distributed algorithm for Delaunay graphs.
Theoretical Computer Science, 457:137–148, Springer-Verlag, 2012. DOI:10.1016/j.tcs.2012.07.029
Conference version: "A Self Stabilizing and Local Delaunay Graph Construction", Proceedings ISAAC 2009 LNCS 5878, 2009, p. 771-780 DOI:10.1007/978-3-642-10631-6_78 © Springer-Verlag isaac09.pdf (284K)
Riko Jacob, Tobias Scheffel, Georg Ziegler, and Martin Bichler.
Hierarchical Package Bidding: Computational Complexity and Bidder Behavior.
Auctions, Market Mechanisms, and Their Applications - Second International ICST Conference, AMMA 2011, New York, NY, USA, August 22-23, 2011, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pages 36-37. Springer, 2011. DOI:10.1007/978-3-642-30913-7_9
Michael A. Bender, Gerth Stolting Brodal, Rolf Fagerberg, Riko Jacob, and Elias Vicari.
Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model.
Theory of Computing Systems, Volume 47, Issue 4 (2010), Page 934. DOI:10.1007/s00224-010-9285-4 © Springer-Verlag TCS_IOBound.pdf (328K).
Conference version: Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures, 2007 IOBound.pdf (312K) © ACM, (2007). This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published as stated, DOI:10.1145/1248377.1248391
Gero Greiner and Riko Jacob.
Evaluating Non-Square Sparse Bilinear Forms on Multiple Vector Pairs in the I/O-Model.
MFCS 2010: Proceedings of the 35th International Symposium on Mathematical Foundations of Computer Science. Springer LNCS Volume 6281, page 393-404. DOI:10.1007/978-3-642-15155-2_35 © Springer-Verlag multiple-bilinear.pdf (360K).
Riko Jacob, Peter Marton, Jens Maue and Marc Nunkesser.
Multistage Methods for Freight Train Classification.
Proceedings ATMOS 2007 - 7th Workshop on Algorithmic Methods and Models for Optimization of Railways. ISBN: 978-3-939897-04-0 DROPS link JMMN07.pdf (248K)
Journal version: Networks 57, pages 87–105, online at: DOI 10.1002/net.20385
Submitted draft (the pre-peer reviewed version of the journal version) jacob-marton-maue-nunkesser.pdf (340K)
Gero Greiner and Riko Jacob.
The I/O Complexity of Sparse Matrix Dense Matrix Multiplication.
In Proc. of 9th Latin American Theoretical Informatics Symposium (LATIN 2010). DOI:10.1007/978-3-642-12200-2_14 Springer LNCS Volume 6034, page 143-156. © Springer-Verlag sparse-dense.pdf (356K).
Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig.
Modeling Scalability in Distributed Self-Stabilization: The Case of Graph Linearization.
In Proc. of 9th Latin American Theoretical Informatics Symposium (LATIN 2010). Springer LNCS Volume 6034, page 294-305. DOI:10.1007/978-3-642-12200-2_27
Full version: TUM-I0835.pdf (348K)
Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig.
A Distributed Polylogarithmic Time Algorithm for Self-Stabilizing Skip Graphs.
Proceedings 28th ACM Symposium on Principles of Distributed Computing (PODC), Calgary, Alberta, Canada, August 2009. DOI:10.1145/1582716.1582741 podc09.pdf (264K)
Deepak Ajwani, Andreas Beckmann, Riko Jacob, Ulrich Meyer, Gabriel Moruz.
On Computational Models for Flash Memory Device.
Experimental Algorithms, (Proceedings SEA 2009). Springer LNCS Volume 5526, page 16. DOI:10.1007/978-3-642-02011-7_4 © Springer-Verlag SEA2009_Flash.pdf (160K)
Jörg Derungs, Riko Jacob, and Peter Widmayer.
Approximate shortest paths guided by a small index.
Algorithmica Vol 57:4 (August 2010). DOI:10.1007/s00453-008-9228-5
Conference version: Proc. Workshop on Algorithms and Data Structures (WADS) 2007 (WADS 07). Springer LNCS Volume 4619, page 553. DOI:10.1007/978-3-540-73951-7_48 © Springer-Verlag excerpt.pdf (204K).
Mark Cieliebak, Alexander Hall, Riko Jacob, and Marc Nunkesser.
Sequential Vector Packing.
Theoretical Computer Science Volume 409, Issue 3, Pages 351-363, (2008). DOI:10.1016/j.tcs.2008.07.027
Conference version: Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 07), Hangzhou, China, April 2007 LNCS 4614, 2007, p. 12-23. DOI:10.1007/978-3-540-74450-4_2 © Springer-Verlag. SVPackCHJN06.pdf (364K)
Riko Jacob.
Binary Search on Two-Dimensional Data.
Technical Report TUM-I0821, Institut für Informatik, Technische Universität München, Juni 08. TUM-I0821.pdf (304K)
Riko Jacob.
Shortest Paths Approaches for Timetable Information.
in "Encyclopedia of Algorithms" Ming-Yang Kao (Ed.), Springer 2008. DOI:10.1007/978-0-387-30162-4_371
Riko Jacob and Michael Schnupp.
Performing Permuting on a Multiprocessor Architecture Using Packet Communication.
Technical Report TUM-I0817, Institut für Informatik, Technische Universität München. TUM-I0817.pdf (284K)
Franz F. Roos, Riko Jacob, Jonas Grossmann, Bernd Fischer, Joachim M. Buhmann, Wilhelm Gruissem, Sacha Baginsky, and Peter Widmayer.
PepSplice: Cache-Efficient Search Algorithms for Comprehensive Identification of Tandem Mass Spectra.
Bioinformatics 2007. DOI:10.1093/bioinformatics/btm417 Direct access at Oxford Journals: Abstract PDF Software:
Riko Jacob.
Optimal Randomized Comparison Based Algorithms for Collision.
In Proc. 32nd International Symposium on Mathematical Foundations of Computer Science, 2007 (MFCS 07). LNCS 4708, 2007, p. 703-714. © Springer-Verlag. DOI:10.1007/978-3-540-74456-6_62 Full version: collision.pdf (212K)
Riko Jacob.
On shunting over a hump.
Technical Report 576, Department of Computer Science ETH Zurich, April 2007. shunting.pdf (184K)
Riko Jacob and Sushant Sachdeva.
I/O Efficieny of Highway Hierarchies.
Technical Report 531, Department of Computer Science ETH Zurich,. TR531.pdf (116K)
M. Gatto, R. Jacob, L. Peeters, and A. Schöbel.
The Computational Complexity of Delay Management.
In Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 05).. 2005 Springer LNCS Volume 3787, page 227-238. DOI:10.1007/11604686_20
Extended version: Technical Report 456, ETH Zurich, 2004. TR456.pdf (176K) (132K)
Michael Gatto, Riko Jacob, and Marc Nunkesser.
Optimization of a Railway Hub-and-Spoke System: Routing and Shunting.
In Poster Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA05), CTI Press, 2005.
Riko Jacob, Dirk Koschützki, Katharina Anna Lehmann, Leon Peeters, and Dagmar Tenfelde-Podehl.
Algorithms for Centrality Indices.
In: Network Analysis: Methodological Foundations, Editors: Ulrik Brandes, Thomas Erlebach, Springer LNCS Volume 3418 / 2005, pp. 62-82. springerlink
M. Gatto, R. Jacob, L. Peeters, and P. Widmayer.
On-Line Delay Management on a Single Line.
In Proceedings Algorithmic Methods and Models for Optimization of Railways (ATMOS) 2004, Springer-Verlag LNCS Volume 4359 (2007) pp. 306-320. springerlink
T. Erlebach, R. Jacob, M. Mihalak, M. Nunkesser, G. Szabo, and P. Widmayer.
Joint Base Station Scheduling.
In Proceedings of the 2nd Workshop on Approximation and Online Algorithms (WAOA). LNCS 3351, 2005, p. 225.. Springer LNCS Volume 3351, page 225. © Springer-Verlag'
Extended version: Technical Report 462, Institute of Theoretical Computer Science, ETH Zürich, December 2004. ps-file, pdf-file
Michael Gatto, Björn Glaus, Riko Jacob, Leon Peeters, and Peter Widmayer.
Railway Delay Management: Exploring its Algorithmic Complexity.
In Proceedings 9th Scandinavian Workshop on Algorithm Theory (SWAT) 2004, Springer LNCS 3111, 2004, pp. 199-211. springerlink © Springer-Verlag. . swat04.pdf (160K) (176K)
Thomas Erlebach, Riko Jacob, Matus Mihalak, Marc Nunkesser, Gabor Szabo, and Peter Widmayer.
An Algorithmic View on OVSF Code Assignment.
Volume 47:3 of Algorithmica . DOI 10.1007/s00453-006-0188-3
Conference version: Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science (STACS 2004), LNCS 2996, Springer-Verlag, March 2004, pp. 270-281. springerlink
Other version: TIK Report Nr. 173, August 2003. gzipped ps-file, pdf-file or from here TIK-Report173.pdf (588K) (748K)
Gerth Brodal and Riko Jacob.
Time-dependent networks as models to achieve fast exact time-table queries.
In Proceedings ATMOS 2003, Electronic Notes in Theoretical Computer Science, Volume 92, 17 February 2004, Pages 3-15.
Other version: Technical Report ALCOMFT-TR-01-176, September 2001 timetable2.pdf (248K) (76K)
Gerth Brodal and Riko Jacob.
Dynamic Planar Convex Hull.
In Proceedings 43rd Annual Symposium on Foundations of Computer Science, 2002. link. dpch.pdf (208K) (76K) Copyright © 2002 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Riko Jacob.
Dynamic Planar Convex Hull.
PhD-Dissertation, BRICS Dissertation Series DS-02-3, February 2002, BRICS, Aarhus. merge.pdf (860K) (576K)
Gerth Brodal, Rolf Fagerberg and Riko Jacob.
Cache-Oblivious Search Trees via Trees of Small Height.
In Proceedings 13th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 39-48, 2002 acm link . soda02.pdf (280K) (212K)
Source code of the programs, our scripts and tools, and the data we present here are available online under
Other version: Technical Report, ALCOMFT-TR-02-53, ALCOM-FT, 20 pages, May 2002 alcomft-tr-02-53.pdf (320K) (208K) ; Technical Report, BRICS-RS-01-36, BRICS, Department of Computer Science, University of Aarhus, 20 pages, October 2001. brics-rs-01-36.pdf (308K) (120K)
Chris Barrett, Keith Bisset, Riko Jacob, Goran Konjevod, and Madhav Marathe.
Classical and Contemporary Shortest Path Problems in Road Networks: Implementation and Experimental Analysis of the TRANSIMS Router.
In Proceedings ESA 2002, LNCS 2461, pp. 126-138, 2002. LNCS-article LNCS-pdf. TRANSIMS_router.pdf (1,5M) © LNCS Springer-Verlag.
Gerth Brodal and Riko Jacob.
Dynamic Planar Convex Hull with Optimal Query Time and O(log n loglog n) Update Time.
In Proceedings 7th Scandinavian Workshop on Algorithm Theory, LNCS 1851, pp. 57-70, 2000. swat2000dch.pdf (244K) (92K) © Springer-Verlag,LNCS
Extended version: Technical Report, ALCOMFT-TR-01-34, ALCOM-FT, 14 pages, April 2001. alcomft-tr-01-34.pdf (268K) (188K)
Christopher L. Barrett, Riko Jacob and Madhav Marathe.
Formal Language Constrained Path Problems.
Siam Journal on Computing, Volume 30, Nr. 3, pp. 809-837, 2000. SIAM epubs. regpath.pdf (444K) (176K)
Conference version: Proceedings of the 6th Skandinavian Workshop on Algorithm Theory Springer LNCS 1432 (SWAT98).
Other version: Technical Report LA-UR-97:2620, Los Alamos National Laboratory.
K. Nagel, M. Rickert, R. Frye, P. Stretz, P. Simon, R. Jacob, and C. L. Barrett.
Regional Transportation Simulations.
Advanced Simulation Technologies Conference, The Society for Computer Simulation International, 1998, LA-UR 98-312. hpc98.pdf (1,2M) (144K)
Riko Jacob, Madhav Marathe, and Kai Nagel.
A Computational Study of Routing Algorithms for Realistic Transportation Networks.
ACM Journal of Experimental Algorithms Vol 4 No 6, 1999. exp-results.pdf (1,5M) (920K)
Other version: LA-UR-98-2249, Proceedings Workshop on Algorithm Engineering (WAE) 98, Saarbrücken.
Riko Jacob.
Standortplanung mit Blick auf Online-Strategien.
(in German) Diplomarbeit Universität Würzburg 1997. arbeit.pdf (560K) (100K)
Riko Jacob.
Quantoren zweiter Stufe zur Darstellung von Zähl- und Optimierungsfunktionen.
(in German) Studienarbeit Universität Würzburg 1996. jacob96.pdf (664K) (156K)

Valid HTML 4.01 Transitional Valid CSS!