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, Andrew V. Goldberg, Matthias Müller–Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  2. Case Studies.
    In: Algorithm Engineering: Bridging the Gap between Algorithm Theory and Practice, volume 5971 of Lecture Notes in Computer Science, pages 389–445. Springer, 2010.
    Joint work with Maria Kandyba, Roberto Hoffmann, and Anna Schulze.
  3. High-Performance Multi-Level Routing.
    In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 73–92. American Mathematical Society, 2009.
    Joint work with Martin Holzer, Kirill Müller, Frank Schulz, and Dorothea Wagner.
    [ pdf ]
  4. 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 Thomas Pajor and Dorothea Wagner.
    [ pdf ]
  5. Engineering Route Planning Algorithms.
    In: Algorithmics of Large and Complex Networks, volume 5515 of Lecture Notes in Computer Science, pages 117–139. Springer, 2009.
    Joint work with Peter Sanders, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  6. Highway Hierarchies Star.
    In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Book, pages 141–174. American Mathematical Society, 2009.
    Joint work with Peter Sanders, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  7. Time-Dependent Route Planning.
    In: Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 207–230. Springer, 2009.
    Joint work with Dorothea Wagner.
    [ pdf ]

Artikel in Zeitschriften

  1. Customizable Route Planning in Road Networks.
    Transportation Science, 51(2):566–591, 2017.
    Joint work with Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck.
    [ html ]
  2. An exact combinatorial algorithm for minimum graph bisection.
    Mathematical Programming, 153(2):417–458, November 2015.
    Joint work with Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck.
  3. Customizable Point-of-Interest Queries in Road Networks.
    IEEE Transactions on Knowledge and Data Engineering, 27(3):686–698, March 2015.
    Joint work with Renato F. Werneck.
  4. Round-Based Public Transit Routing.
    Transportation Science, 49(3):591–604, 2015.
    Joint work with Thomas Pajor and Renato F. Werneck.
    [ html ]
  5. An Exact Combinatorial Algorithm for Minimum Graph Bisection.
    Mathematical Programming, Series A, 2014.
    to appear.
    Joint work with Daniel Fleischman, Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck.
  6. On d-regular Schematization of Embedded Paths.
    Computational Geometry: Theory and Applications, 47(3A):381–406, 2014.
    Joint work with Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
    [ html | pdf ]
  7. Highway dimension and provably efficient shortest path algorithms.
    Journal of the ACM, 63(5):41:1–41:26, December 2013.
    Joint work with Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck.
  8. Alternative Routes in Road Networks.
    ACM Journal of Experimental Algorithmics, 18(1):1–17, 2013.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
  9. PHAST: Hardware-accelerated shortest path trees.
    Journal of Parallel and Distributed Computing, 73(7):940–952, 2013.
    Joint work with Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck.
    [ html | pdf ]
  10. From Destination Prediction to Route Prediction.
    Journal of Location Based Services, 7(2):98–120, 2013.
    Joint work with John Krumm and Robert Gruen.
  11. 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 Bastian Katz and Thomas Pajor.
    [ html ]
  12. The Shortcut Problem – Complexity and Algorithms.
    Journal of Graph Algorithms and Applications, 16(2):447–481, 2012.
    Joint work with Reinhard Bauer, Gianlorenzo D'Angelo, Andrea Schumm, and Dorothea Wagner.
    [ html ]
  13. Core Routing on Dynamic Time-Dependent Road Networks.
    Informs Journal on Computing, 24(2):187–201, 2012.
    Joint work with Giacomo Nannicini.
  14. Bidirectional A* Search on Time-Dependent Road Networks.
    Networks, 59:240–251, 2012.
    Best Paper Award.
    Joint work with Giacomo Nannicini, Leo Liberti, and Dominik Schultes.
  15. Shortest Paths in Road Networks: From Practice to Theory and Back.
    it—Information Technology, 53:294–301, December 2011.
    Joint work with Andrew V. Goldberg and Renato F. Werneck.
    [ html ]
  16. Time-Dependent SHARC-Routing.
    Algorithmica, 60(1):60–94, May 2011.
    [ html | pdf ]
  17. Experimental Study on Speed-Up Techniques for Timetable Information Systems.
    Networks, 57(1):38–52, January 2011.
    Joint work with Reinhard Bauer and Dorothea Wagner.
    [ pdf ]
  18. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm.
    ACM Journal of Experimental Algorithmics, 15(2.3):1–31, January 2010.
    Special Section devoted to WEA'08.
    Joint work with Reinhard Bauer, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  19. SHARC: Fast and Robust Unidirectional Routing.
    ACM Journal of Experimental Algorithmics, 14(2.4):1–29, August 2009.
    Special Section on Selected Papers from ALENEX 2008.
    Joint work with Reinhard Bauer.
    [ html | pdf ]
  20. On Modularity Clustering.
    IEEE Transactions on Knowledge and Data Engineering, 20(2):172–188, February 2008.
    Joint work with Ulrik Brandes, Marco Gaertler, Robert Görke, Martin Höfer, Zoran Nikoloski, and Dorothea Wagner.
    [ html ]
  21. Computergestützte Spracherkennung.
    Der Pathologe, 20:115–119, 1999.
    Joint work with Günter Delling.

Artikel in Tagungsbänden

  1. Fast and Stable Repartitioning of Road Networks.
    In: Proceedings of the 18th International Symposium on Experimental Algorithms (SEA'20), volume 160 of Leibniz International Proceedings in Informatics, pages 26:1–26:15, June 2020.
    Joint work with Valentin Buchhold, Dennis Schieferdecker, and Michael Wegner.
    [ html | pdf ]
  2. 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 Julian Dibbelt and Thomas Pajor.
  3. Traffic-Aware Routing in Road Networks.
    In: Proceedings of the 34rd International Conference on Data Engineering. IEEE Computer Society, 2018.
    Joint work with Dennis Schieferdecker and Christian Sommer.
    [ html ]
  4. 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 Julian Dibbelt, Thomas Pajor, and Tobias Zündorf.
    [ html | pdf ]
  5. On dynamic approximate shortest paths for planar graphs with worst-case costs.
    In: Proceedings of the 27th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'16), pages 740–753. SIAM, 2016.
    Joint work with Ittai Abraham, Shiri Chechik, Andrew V. Goldberg, and Renato F. Werneck.
  6. 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 Julian Dibbelt, Thomas Pajor, and Renato F. Werneck.
    [ html ]
  7. Navigation Made Personal: Inferring Driving Preferences from GPS Traces.
    In: Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM Press, 2015.
    Joint work with Andrew V. Goldberg, Moises Goldszmidt, John Krumm, Kunal Talwar, and Renato F. Werneck.
  8. 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 Giuseppe F. Italiano, Thomas Pajor, and Federico Santaroni.
  9. 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 Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck.
  10. 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, Thomas Pajor, and Renato F. Werneck.
  11. 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, Thomas Pajor, and Renato F. Werneck.
    [ html ]
  12. Hub Labels: Theory and Practice.
    In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14), volume 8504 of Lecture Notes in Computer Science, pages 259–270. Springer, 2014.
    Joint work with Andrew V. Goldberg, Ruslan Savchenko, and Renato F. Werneck.
  13. Customizing Driving Directions with GPUs.
    In: Proceedings of the 20th International Conference on Parallel Processing (Euro-Par 2014), volume 8632 of Lecture Notes in Computer Science, pages 728–739. Springer, 2014.
    Joint work with Moritz Kobitzsch and Renato F. Werneck.
  14. Scalable Similarity Estimation in Social Networks: Closeness, Node Labels, and Random Edge Lengths.
    In: Proceedings of the ACM Conference on Online Social Networks (COSN'13), volume 1, pages 131–142. ACM Press, October 2013.
    Joint work with Edith Cohen, Fabian Fuchs, Andrew V. Goldberg, Moises Goldszmidt, and Renato F. Werneck.
    [ pdf ]
  15. 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 Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck.
    [ pdf ]
  16. Hub Label Compression.
    In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 18–29. Springer, 2013.
    Joint work with Andrew V. Goldberg and Renato F. Werneck.
  17. Customizable Point-of-Interest Queries in Road Networks.
    In: Proceedings of the 21st ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS'13), pages 490–493. ACM Press, 2013.
    Joint work with Renato F. Werneck.
  18. Faster Customization of Road Networks.
    In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13), volume 7933 of Lecture Notes in Computer Science, pages 30–42. Springer, 2013.
    Joint work with Renato F. Werneck.
  19. HLDB: Location-Based Services in Databases.
    In: Proceedings of the 20th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems (GIS'12), pages 339–348. ACM Press, 2012.
    Best Paper Award.
    Joint work with Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck.
    [ pdf ]
  20. Hierarchical Hub Labelings for Shortest Paths.
    In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 24–35. Springer, 2012.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
    [ pdf ]
  21. Exact Combinatorial Branch-and-Bound for Graph Bisection.
    In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 30–44. SIAM, 2012.
    Joint work with Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck.
  22. Robust Mobile Route Planning with Limited Connectivity.
    In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12), pages 150–159. SIAM, 2012.
    Joint work with Moritz Kobitzsch, Dennis Luxen, and Renato F. Werneck.
    [ pdf ]
  23. 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 Thomas Pajor and Renato F. Werneck.
    [ html | pdf ]
  24. Better Bounds for Graph Bisection.
    In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA'12), volume 7501 of Lecture Notes in Computer Science, pages 407–418. Springer, 2012.
    Joint work with Renato F. Werneck.
    [ pdf ]
  25. VC-Dimension and Shortest Path Algorithms.
    In: Proceedings of the 38th International Colloquium on Automata, Languages, and Programming (ICALP'11), volume 6755 of Lecture Notes in Computer Science, pages 690–699. Springer, 2011.
    Joint work with Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck.
  26. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks.
    In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 230–241. Springer, 2011.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
  27. DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines.
    In: 25th International Parallel and Distributed Processing Symposium (IPDPS'11), pages 1278–1289. IEEE Computer Society, 2011.
    Joint work with Mihai Budiu and Renato F. Werneck.
  28. PHAST: Hardware-Accelerated Shortest Path Trees.
    In: 25th International Parallel and Distributed Processing Symposium (IPDPS'11), pages 921–931. IEEE Computer Society, 2011.
    Best Paper Award - Algorithms Track.
    Joint work with Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck.
  29. 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 Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck.
    [ pdf ]
  30. Graph Partitioning with Natural Cuts.
    In: 25th International Parallel and Distributed Processing Symposium (IPDPS'11), pages 1135–1146. IEEE Computer Society, 2011.
    Joint work with Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck.
  31. Faster Batched Shortest Paths in Road Networks.
    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 52–63, 2011.
    Joint work with Andrew V. Goldberg and Renato F. Werneck.
  32. 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 Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  33. Alternative Routes in Road Networks.
    In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 23–34. Springer, May 2010.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
    [ html ]
  34. Space-Efficient SHARC-Routing.
    In: Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10), volume 6049 of Lecture Notes in Computer Science, pages 47–58. Springer, May 2010.
    Joint work with Edith Brunel, Andreas Gemsa, and Dorothea Wagner.
    [ pdf ]
  35. 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 Bastian Katz and Thomas Pajor.
    [ pdf ]
  36. 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 Thomas Pajor and Dorothea Wagner.
    [ pdf ]
  37. ORCA Reduction and ContrAction Graph Clustering.
    In: Proceedings of the 5th International Conference on Algorithmic Aspects in Information and Management (AAIM'09), volume 5564 of Lecture Notes in Computer Science, pages 152–165. Springer, June 2009.
    Joint work with Robert Görke, Christian Schulz, and Dorothea Wagner.
    [ html | pdf ]
  38. Pareto Paths with SHARC.
    In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09), volume 5526 of Lecture Notes in Computer Science, pages 125–136. Springer, June 2009.
    Joint work with Dorothea Wagner.
    [ pdf ]
  39. Time-Dependent Contraction Hierarchies.
    In: Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09), pages 97–105. SIAM, April 2009.
    Joint work with Gernot Veit Batz, Peter Sanders, and Christian Vetter.
    [ pdf ]
  40. Arc-Flags in Dynamic Graphs.
    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 Emanuele Berretini and Gianlorenzo D'Angelo.
    [ pdf ]
  41. The Shortcut Problem – Complexity and Approximation.
    In: Proceedings of the 35th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'09), volume 5404 of Lecture Notes in Computer Science, pages 105–116. Springer, January 2009.
    Joint work with Reinhard Bauer, Gianlorenzo D'Angelo, and Dorothea Wagner.
    [ pdf ]
  42. Accelerating Time-Dependent Multi-Criteria Timetable Information is Harder Than Expected.
    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 Annabell Berger, Andreas Gebhardt, and Matthias Müller–Hannemann.
    [ pdf ]
  43. 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 Thomas Pajor, Dorothea Wagner, and Christos Zaroliagis.
    [ pdf ]
  44. Bidirectional Core-Based Routing in Dynamic Time-Dependent Road Networks.
    In: Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC'08), volume 5369 of Lecture Notes in Computer Science, pages 813–824. Springer, December 2008.
    Joint work with Giacomo Nannicini.
    [ pdf ]
  45. Time-Dependent SHARC-Routing.
    In: Proceedings of the 16th Annual European Symposium on Algorithms (ESA'08), volume 5193 of Lecture Notes in Computer Science, pages 332–343. Springer, September 2008.
    Best Student Paper Award - ESA Track B.
    [ pdf ]
  46. 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 Thomas Pajor and Dorothea Wagner.
    [ pdf ]
  47. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm.
    In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 303–318. Springer, June 2008.
    Joint work with Reinhard Bauer, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  48. Engineering Comparators for Graph Clusterings.
    In: Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM'08), volume 5034 of Lecture Notes in Computer Science, pages 131–142. Springer, June 2008.
    Joint work with Marco Gaertler, Robert Görke, and Dorothea Wagner.
    [ pdf ]
  49. Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks.
    In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 319–333. Springer, June 2008.
    Joint work with Robert Geisberger, Peter Sanders, and Dominik Schultes.
    [ pdf ]
  50. Bidirectional A* Search for Time-Dependent Fast Paths.
    In: Proceedings of the 7th Workshop on Experimental Algorithms (WEA'08), volume 5038 of Lecture Notes in Computer Science, pages 334–346. Springer, June 2008.
    Joint work with Giacomo Nannicini, Leo Liberti, and Dominik Schultes.
    [ pdf ]
  51. SHARC: Fast and Robust Unidirectional Routing.
    In: Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX'08), pages 13–26. SIAM, April 2008.
    Joint work with Reinhard Bauer.
    [ pdf ]
  52. On Finding Graph Clusterings with Maximum Modularity.
    In: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'07), volume 4769 of Lecture Notes in Computer Science, pages 121–132. Springer, October 2007.
    Joint work with Ulrik Brandes, Martin Höfer, Marco Gaertler, Robert Görke, Zoran Nikoloski, and Dorothea Wagner.
    [ html | pdf ]
  53. Evaluating Clustering Techniques - An Engineering Approach Inspired by Unit-Tests.
    In: Proceedings of the European Conference of Complex Systems (ECCS'07), October 2007.
    Poster.
    Joint work with Marco Gaertler, Robert Görke, Zoran Nikoloski, and Dorothea Wagner.
    [ html | pdf ]
  54. Engineering Comparators for Graph Clusterings.
    In: Proceedings of the European Conference of Complex Systems (ECCS'07), October 2007.
    as poster.
    Joint work with Marco Gaertler, Robert Görke, and Dorothea Wagner.
    [ html | pdf ]
  55. Landmark-Based Routing in Dynamic Graphs.
    In: Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), volume 4525 of Lecture Notes in Computer Science, pages 52–65. Springer, June 2007.
    Joint work with Dorothea Wagner.
    [ html | pdf ]
  56. Experimental Study on Speed-Up Techniques for Timetable Information Systems.
    In: Proceedings of the 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07), OpenAccess Series in Informatics (OASIcs), pages 209–225, 2007.
    Joint work with Reinhard Bauer and Dorothea Wagner.
    [ html | pdf ]
  57. High-Performance Multi-Level Graphs.
    In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge -, November 2006.
    Joint work with Martin Holzer, Kirill Müller, Frank Schulz, and Dorothea Wagner.
    [ html | pdf ]
  58. Highway Hierarchies Star.
    In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge -, November 2006.
    Joint work with Peter Sanders, Dominik Schultes, and Dorothea Wagner.
    [ html | pdf ]
  59. Generating Significant Graph Clusterings.
    In: Proceedings of the European Conference of Complex Systems (ECCS'06), September 2006.
    Joint work with Marco Gaertler and Dorothea Wagner.
    [ html | pdf ]

Dissertation

  1. Engineering and Augmenting Route Planning Algorithms.
    PhD thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2009.
    [ html | pdf ]

Abschlussarbeiten

  1. Analyse und Evaluierung von Vergleichsmaßen für Graphclusterungen.
    Diplomarbeit, Universität Karlsruhe (TH), Fakultät für Informatik, February 2006.
    [ pdf ]

Technische Berichte

  1. 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, Andrew V. Goldberg, Matthias Müller–Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  2. Robust Exact Distance Queries on Massive Networks.
    Technical report, Microsoft Research, 2014.
    Joint work with Andrew V. Goldberg, Thomas Pajor, and Renato F. Werneck.
  3. Highway Dimension and Provably Efficient Shortest Path Algorithms.
    Technical Report MSR-TR-2013-91, Microsoft Research, 2013.
    Joint work with Ittai Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck.
    [ html ]
  4. Hierarchical Hub Labelings for Shortest Paths.
    Technical Report MSR-TR-2012-46, Microsoft Research, 2012.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
    [ pdf ]
  5. Computing and Evaluating Multimodal Journeys.
    Technical Report 2012-20, Faculty of Informatics, Karlsruhe Institute of Technology, 2012.
    Joint work with Julian Dibbelt, Thomas Pajor, Dorothea Wagner, and Renato F. Werneck.
    [ html | pdf ]
  6. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks.
    Technical Report MSR-TR-2010-165, Microsoft Research, 2010.
    Joint work with Ittai Abraham, Andrew V. Goldberg, and Renato F. Werneck.
  7. The Shortcut Problem – Complexity and Algorithms.
    Technical Report 2010-17, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2010.
    Joint work with Reinhard Bauer, Gianlorenzo D'Angelo, Andrea Schumm, and Dorothea Wagner.
    [ html ]
  8. Path Schematization for Route Sketches.
    Technical Report 2010-02, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    [ html | pdf ]
  9. PHAST: Hardware-Accelerated Shortest Path Trees.
    Technical Report MSR-TR-2010-125, Microsoft Research, 2010.
    Joint work with Andrew V. Goldberg, Andreas Nowatzyk, and Renato F. Werneck.
  10. Graph Partitioning with Natural Cuts.
    Technical Report MSR-TR-2010-164, Microsoft Research, 2010.
    Joint work with Andrew V. Goldberg, Ilya Razenshteyn, and Renato F. Werneck.
  11. Space-Efficient SHARC-Routing.
    Technical Report 13, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Edith Brunel, Andreas Gemsa, and Dorothea Wagner.
    [ pdf ]
  12. Parallel Computation of Best Connections in Public Transportation Networks.
    Technical Report 2009-16, Faculty of Informatics, Karlsruhe Institute of Technology, 2009.
    Joint work with Bastian Katz and Thomas Pajor.
    [ pdf ]
  13. Impact of Shortcuts on Speedup Techniques.
    Technical Report 2008-10, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2008.
    Joint work with Reinhard Bauer and Dorothea Wagner.
    [ pdf ]
  14. Contracting Timetable Information Networks.
    Technical Report 144, Arrival Technical Report, 2008.
    Joint work with Kalliopi Giannakopoulou, Dorothea Wagner, and Christos Zaroliagis.
    [ pdf ]
  15. Timetable Information Updating in Case of Delays: Modeling Issues.
    Technical Report 133, Arrival Technical Report, 2008.
    Joint work with Kalliopi Giannakopoulou, Dorothea Wagner, and Christos Zaroliagis.
    [ pdf ]
  16. The Complexity of the Shortcut Problem.
    Technical Report 117, Arrival Technical Report, 2007.
    Joint work with Reinhard Bauer, Gianlorenzo D'Angelo, and Dorothea Wagner.
    [ pdf ]
  17. Shortest-Path Indices: Establishing a Methodology for Shortest-Path Problems.
    Technical Report 2007-14, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2007.
    Joint work with Reinhard Bauer and Dorothea Wagner.
    [ html | pdf ]
  18. On Modularity - NP-Completeness and Beyond.
    Technical Report 2006-19, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2006.
    Joint work with Ulrik Brandes, Marco Gaertler, Robert Görke, Martin Höfer, Zoran Nikoloski, and Dorothea Wagner.
    [ html | pdf ]
  19. How to Evaluate Clustering Techniques.
    Technical Report 2006-24, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2006.
    Joint work with Marco Gaertler, Robert Görke, Zoran Nikoloski, and Dorothea Wagner.
    [ html | pdf ]
  20. Experiments on Comparing Graph Clusterings.
    Technical Report 2006-16, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2006.
    Joint work with Marco Gaertler, Robert Görke, and Dorothea Wagner.
    [ html | pdf ]