Institut für Theoretische Informatik, Algorithmik

Veröffentlichungen

Buchbeiträge

  1. Route Planning in Transportation Networks.
    In: Algorithm Engineering - Selected Results and Surveys, volume 9220 of Lecture Notes in Computer Science, pages 19–80. Springer, 2016.
    Joint work with Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller–Hannemann, Peter Sanders, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  2. Engineering Time-Expanded Graphs for Faster Timetable Information.
    In: Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 182–206. Springer, 2009.
    Joint work with Daniel Delling and Dorothea Wagner.
    [ pdf ]

Artikel in Zeitschriften

  1. Energy-Optimal Routes for Battery Electric Vehicles.
    Algorithmica, 82(5):1490–1546, 2019.
    Joint work with Moritz Baum, Julian Dibbelt, Jonas Sauer, Dorothea Wagner, and Tobias Zündorf.
    [ html | pdf ]
  2. Connection Scan Algorithm.
    ACM Journal of Experimental Algorithmics, 23(1):1.7:1–1.7:56, October 2018.
    Joint work with Julian Dibbelt, Ben Strasser, and Dorothea Wagner.
    [ html | pdf ]
  3. Customizable Route Planning in Road Networks.
    Transportation Science, 51(2):566–591, 2017.
    Joint work with Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck.
    [ html ]
  4. User-Constrained Multi-Modal Route Planning.
    ACM Journal of Experimental Algorithmics, 19:3.2:1.1–3.2:1.19, April 2015.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ html ]
  5. Round-Based Public Transit Routing.
    Transportation Science, 49(3):591–604, 2015.
    Joint work with Daniel Delling and Renato F. Werneck.
    [ html ]
  6. On d-regular Schematization of Embedded Paths.
    Computational Geometry: Theory and Applications, 47(3A):381–406, 2014.
    Joint work with Daniel Delling, Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    [ html | pdf ]
  7. Parallel Computation of Best Connections in Public Transportation Networks.
    ACM Journal of Experimental Algorithmics, 17(4):4.1–4.26, July 2012.
    Joint work with Daniel Delling and Bastian Katz.
    [ html ]

Artikel in Tagungsbänden

  1. Fast and Exact Public Transit Routing with Restricted Pareto Sets.
    In: Proceedings of the 21st Meeting on Algorithm Engineering and Experiments (ALENEX'19), pages 54–65. SIAM, January 2019.
    Joint work with Daniel Delling and Julian Dibbelt.
  2. Faster Transit Routing by Hyper Partitioning.
    In: Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'17), volume 59 of OpenAccess Series in Informatics (OASIcs), pages 8:1–8:14, 2017.
    Joint work with Daniel Delling, Julian Dibbelt, and Tobias Zündorf.
    [ html | pdf ]
  3. Dynamic Time-Dependent Route Planning in Road Networks with User Preferences.
    In: Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16), volume 9685 of Lecture Notes in Computer Science, pages 33–49. Springer, June 2016.
    Joint work with Moritz Baum, Julian Dibbelt, and Dorothea Wagner.
    [ html ]
  4. Towards Realistic Pedestrian Route Planning.
    In: Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'15), volume 48 of OpenAccess Series in Informatics (OASIcs), pages 1–15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, September 2015.
    Joint work with Simeon Danailov Andreev, Julian Dibbelt, Martin Nöllenburg, and Dorothea Wagner.
    [ pdf ]
  5. Public Transit Labeling.
    In: Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15), Lecture Notes in Computer Science, pages 273–285. Springer, 2015.
    Joint work with Daniel Delling, Julian Dibbelt, and Renato F. Werneck.
    [ html ]
  6. Better Transit Routing by Exploiting Vehicle GPS Data.
    In: Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science. ACM Press, November 2014.
    Joint work with Daniel Delling, Giuseppe F. Italiano, and Federico Santaroni.
  7. Robust Distance Queries on Massive Networks.
    In: Proceedings of the 22nd Annual European Symposium on Algorithms (ESA'14), volume 8737 of Lecture Notes in Computer Science, pages 321–333. Springer, September 2014.
    Joint work with Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck.
  8. Speed-Consumption Tradeoff for Electric Vehicle Route Planning.
    In: Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14), volume 42 of OpenAccess Series in Informatics (OASIcs), pages 138–151. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
    Joint work with Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, and Dorothea Wagner.
    [ html | pdf ]
  9. Computing Classic Closeness Centrality, at Scale .
    In: Proceedings of the 2nd ACM Conference on Online Social Networks (COSN'14). ACM Press, 2014.
    Best Paper Award.
    Joint work with Edith Cohen, Daniel Delling, and Renato F. Werneck.
  10. Sketch-based Influence Maximization and Computation: Scaling up with Guarantees.
    In: Proceedings of the 23rd International Conference on Information and Knowledge Management, pages 629–638. ACM Press, 2014.
    Joint work with Edith Cohen, Daniel Delling, and Renato F. Werneck.
    [ html ]
  11. Energy-Optimal Routes for Electric Vehicles.
    In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 54–63. ACM Press, 2013.
    Joint work with Moritz Baum, Julian Dibbelt, and Dorothea Wagner.
    [ html ]
  12. Computing Multimodal Journeys in Practice.
    In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 260–271. Springer, 2013.
    Joint work with Daniel Delling, Julian Dibbelt, Dorothea Wagner, and Renato F. Werneck.
    [ pdf ]
  13. Intriguingly Simple and Fast Transit Routing.
    In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 43–54. Springer, 2013.
    Joint work with Julian Dibbelt, Ben Strasser, and Dorothea Wagner.
    [ pdf ]
  14. Efficient Computation of Jogging Routes.
    In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 272–283. Springer, 2013.
    Joint work with Andreas Gemsa, Dorothea Wagner, and Tobias Zündorf.
    [ html | pdf ]
  15. Round-Based Public Transit Routing.
    In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 130–140. SIAM, 2012.
    Joint work with Daniel Delling and Renato F. Werneck.
    [ html | pdf ]
  16. User-Constrained Multi-Modal Route Planning.
    In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 118–129. SIAM, 2012.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ pdf ]
  17. Customizable Route Planning.
    In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 376–387. Springer, 2011.
    Joint work with Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck.
    [ pdf ]
  18. Automatic Generation of Route Sketches.
    In: Proceedings of the 18th International Symposium on Graph Drawing (GD'10), volume 6502 of Lecture Notes in Computer Science, pages 391–392. Springer, 2011.
    Poster abstract.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    [ html | pdf ]
  19. On d-regular Schematization of Embedded Paths.
    In: Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'11), volume 6543 of Lecture Notes in Computer Science, pages 260–271. Springer, January 2011.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    [ html | pdf ]
  20. UniALT for Regular Language Constraint Shortest Paths on a Multi-Modal Transportation Network.
    In: Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11), volume 20 of OpenAccess Series in Informatics (OASIcs), pages 64–75, 2011.
    Joint work with Dominik Kirchler, Leo Liberti, and Roberto Wolfler Calvo.
    [ html | pdf ]
  21. Path Schematization for Route Sketches.
    In: Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'10), volume 6139 of Lecture Notes in Computer Science, pages 285–296. Springer, June 2010.
    Joint work with Daniel Delling, Andreas Gemsa, and Martin Nöllenburg.
    [ html | pdf ]
  22. Parallel Computation of Best Connections in Public Transportation Networks.
    In: 24th International Parallel and Distributed Processing Symposium (IPDPS'10), pages 1–12. IEEE Computer Society, 2010.
    Joint work with Daniel Delling and Bastian Katz.
    [ pdf ]
  23. Accelerating Multi-Modal Route Planning by Access-Nodes.
    In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09), volume 5757 of Lecture Notes in Computer Science, pages 587–598. Springer, September 2009.
    Joint work with Daniel Delling and Dorothea Wagner.
    [ pdf ]
  24. Efficient Route Planning in Flight Networks.
    In: Proceedings of the 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09), OpenAccess Series in Informatics (OASIcs), 2009.
    Joint work with Daniel Delling, Dorothea Wagner, and Christos Zaroliagis.
    [ pdf ]
  25. Engineering Time-Expanded Graphs for Faster Timetable Information.
    In: Proceedings of the 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), OpenAccess Series in Informatics (OASIcs), September 2008.
    Joint work with Daniel Delling and Dorothea Wagner.
    [ pdf ]

Dissertation

  1. Algorithm Engineering for Realistic Journey Planning in Transportation Networks.
    PhD thesis, Karlsruhe Institute of Technology, November 2013.
    [ html | pdf ]

Abschlussarbeiten

  1. Multi-Modal Route Planning.
    Master's thesis, Universität Karlsruhe (TH), March 2009.
    [ html ]

Technische Berichte

  1. Connection Scan Algorithm.
    Technical report, ArXiv e-prints, 2017.
    Joint work with Julian Dibbelt, Ben Strasser, and Dorothea Wagner.
    [ html ]
  2. Route Planning in Transportation Networks.
    Technical Report abs/1504.05140, ArXiv e-prints, 2016.
    To appear in LNCS Volume on Algorithm Engineering, Lasse Kliemann and Peter Sanders (eds.).
    Joint work with Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller–Hannemann, Peter Sanders, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  3. Dynamic Time-Dependent Route Planning in Road Networks with User Preferences.
    Technical Report 1512.09132, ArXiv e-prints, 2015.
    Joint work with Moritz Baum, Julian Dibbelt, and Dorothea Wagner.
    [ html | pdf ]
  4. Robust Exact Distance Queries on Massive Networks.
    Technical report, Microsoft Research, 2014.
    Joint work with Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck.
  5. Energy-Optimal Routes for Electric Vehicles.
    Technical Report 2013-06, Faculty of Informatics, Karlsruhe Institute of Technology, 2013.
    Joint work with Moritz Baum, Julian Dibbelt, and Dorothea Wagner.
    [ html | pdf ]
  6. Computing and Evaluating Multimodal Journeys.
    Technical Report 2012-20, Faculty of Informatics, Karlsruhe Institute of Technology, 2012.
    Joint work with Daniel Delling, Julian Dibbelt, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  7. Path Schematization for Route Sketches.
    Technical Report 2010-02, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Daniel Delling, Andreas Gemsa, and Martin Nöllenburg.
    [ html | pdf ]
  8. On d-regular Schematization of Embedded Paths.
    Technical Report 2010-21, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    [ html | pdf ]
  9. Parallel Computation of Best Connections in Public Transportation Networks.
    Technical Report 2009-16, Faculty of Informatics, Karlsruhe Institute of Technology, 2009.
    Joint work with Daniel Delling and Bastian Katz.
    [ pdf ]