Institute of Theoretical Informatics, Algorithmics

Publications

Book chapters

  1. Graph Fill-In, Elimination Ordering, Nested Dissection and Contraction Hierarchies.
    In: Gems of Combinatorial Optimization and Graph Algorithms, pages 69–82. Springer, December 2015.
    Joint work with Dorothea Wagner.
    [ html ]

Journal articles

  1. Using Incremental Many-to-One Queries to Build a Fast and Tight Heuristic for A* in Road Networks.
    ACM Journal of Experimental Algorithmics, 2022.
    Joint work with Tim Zeitz.
    [ html ]
  2. Space-efficient, Fast and Exact Routing in Time-Dependent Road Networks.
    Algorithms, 14(3), January 2021.
    Joint work with Dorothea Wagner and Tim Zeitz.
    [ html ]
  3. Integrating public transport into mobiTopp.
    Future Generation Computer Systems, 107:1089–1096, 2020.
    Joint work with Lars Briem, H. Sebastian Buck, Nicolai Mallig, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf.
    [ html ]
  4. Correspondence between Multilevel Graph Partitions and Tree Decompositions.
    Algorithms, 12(9):198, 2019.
    Joint work with Michael Hamann.
    [ html | pdf ]
  5. Connection Scan Algorithm.
    ACM Journal of Experimental Algorithmics, 23(1):1.7:1–1.7:56, October 2018.
    Joint work with Julian Dibbelt, Thomas Pajor, and Dorothea Wagner.
    [ html | pdf ]
  6. Graph Bisection with Pareto Optimization.
    ACM Journal of Experimental Algorithmics, 23(1):1.2:1–1.2:34, 2018.
    Joint work with Michael Hamann.
    [ html ]
  7. Computing Tree Decompositions with FlowCutter: PACE 2017 Submission.
    CoRR, 2017.
    [ html ]
  8. Customizable Contraction Hierarchies.
    ACM Journal of Experimental Algorithmics, 21(1):1.5:1–1.5:49, April 2016.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ html ]
  9. Compressing Optimal Paths with Run Length Encoding.
    Journal of Artificial Intelligence Research, 54:593–629, 2015.
    Joint work with Adi Botea and Daniel Harabor.
    [ html ]

Conference articles

  1. A Fast and Tight Heuristic for A* in Road Networks.
    In: Proceedings of the 19th International Symposium on Experimental Algorithms (SEA'21), volume 190 of Leibniz International Proceedings in Informatics, June 2021.
    Joint work with Tim Zeitz.
    [ html ]
  2. Space-efficient, Fast and Exact Routing in Time-dependent Road Networks.
    In: Proceedings of the 28th Annual European Symposium on Algorithms (ESA'20), Leibniz International Proceedings in Informatics, September 2020.
    Joint work with Dorothea Wagner and Tim Zeitz.
    [ html ]
  3. Engineering Exact Quasi-Threshold Editing.
    In: Proceedings of the 18th International Symposium on Experimental Algorithms (SEA'20), volume 160 of Leibniz International Proceedings in Informatics, pages 10:1–10:14, June 2020.
    Joint work with Lars Gottesbüren, Michael Hamann, Philipp Schoch, Dorothea Wagner, and Sven Zühlsdorf.
    [ html | pdf ]
  4. Distributed Graph Clustering Using Modularity and Map Equation.
    In: Proceedings of the 24th International Conference on Parallel Processing (Euro-Par 2018), volume 11014 of Lecture Notes in Computer Science, pages 688–702. Springer, 2018.
    Joint work with Michael Hamann, Dorothea Wagner, and Tim Zeitz.
    [ html ]
  5. Efficient Traffic Assignment for Public Transit Networks.
    In: Proceedings of the 16th International Symposium on Experimental Algorithms (SEA'17), volume 75 of Leibniz International Proceedings in Informatics, pages 20:1–20:14, 2017.
    Joint work with Lars Briem, H. Sebastian Buck, Holger Ebhart, Nicolai Mallig, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf.
    [ html | pdf ]
  6. Integrating public transport into mobiTopp.
    In: Proceedings of the 6th International Workshop on Agent-based Mobility, Traffic and Transportation Models, Methodologies and Applications (ABMTRANS'17), pages 855–860. Elsevier B.V., 2017.
    Joint work with Lars Briem, H. Sebastian Buck, Nicolai Mallig, Peter Vortisch, Dorothea Wagner, and Tobias Zündorf.
    [ html | pdf ]
  7. Dynamic Time-Dependent Routing in Road Networks Through Sampling.
    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 3:1–3:17, 2017.
    [ html | pdf ]
  8. Graph Bisection with Pareto-Optimization.
    In: Proceedings of the 18th Meeting on Algorithm Engineering and Experiments (ALENEX'16), pages 90–102. SIAM, 2016.
    Joint work with Michael Hamann.
  9. The Grid-Based Path Planning Competition: 2014 Entries and Results.
    In: Proceedings of the 6th International Symposium on Combinatorial Search (SoCS'15). AAAI Press, June 2015.
    Joint work with Nathan Sturtevant, Jason Traish, James Tulip, Tansel Uras, Sven Koenig, Adi Botea, Daniel Harabor, and Steve Rabin.
    [ html ]
  10. Fast Quasi-Threshold Editing.
    In: Proceedings of the 23rd Annual European Symposium on Algorithms (ESA'15), volume 9294 of Lecture Notes in Computer Science, pages 251–262. Springer, 2015.
    Joint work with Ulrik Brandes, Michael Hamann, and Dorothea Wagner.
  11. Complexity Results for Compressing Optimal Paths .
    In: Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, pages 1100–1106. AAAI Press, 2015.
    Joint work with Adi Botea and Daniel Harabor.
  12. Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs.
    In: Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 66:1–66:4. ACM Press, 2015.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ pdf ]
  13. Fast First-Move Queries through Run-Length Encoding.
    In: Proceedings of the 5th International Symposium on Combinatorial Search (SoCS'14), pages 157–165. AAAI Press, July 2014.
    Joint work with Daniel Harabor and Adi Botea.
  14. Customizable Contraction Hierarchies.
    In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14), volume 8504 of Lecture Notes in Computer Science, pages 271–282. Springer, 2014.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ pdf ]
  15. Delay-Robust Journeys in Timetable Networks with Minimum Expected Arrival Time.
    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 2:1–2:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ pdf ]
  16. Connection Scan Accelerated.
    In: Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX'14), pages 125–137. SIAM, 2014.
    Joint work with Dorothea Wagner.
  17. 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, Thomas Pajor, and Dorothea Wagner.
    [ pdf ]
  18. Speed Dating: An Algorithmic Case Study Involving Matching and Scheduling.
    In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11), volume 6630 of Lecture Notes in Computer Science, pages 292–303. Springer, 2011.
    Joint work with Bastian Katz, Ignaz Rutter, and Dorothea Wagner.

Master's Thesis

  1. Delay-Robust Stochastic Routing in Timetable Networks.
    Diploma thesis, July 2012.
    [ pdf ]

Technical reports

  1. Engineering Exact Quasi-Threshold Editing.
    Technical report, arXiv, 2020.
    Joint work with Lars Gottesbüren, Michael Hamann, Philipp Schoch, Dorothea Wagner, and Sven Zühlsdorf.
    [ html ]
  2. Space-efficient, Fast and Exact Routing in Time-dependent Road Networks.
    Technical report, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2019.
    Joint work with Dorothea Wagner and Tim Zeitz.
    [ html ]
  3. A Fast and Tight Heuristic for A* in Road Networks.
    Technical report, ITI Wagner, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2019.
    Joint work with Tim Zeitz.
    [ html ]
  4. Connection Scan Algorithm.
    Technical report, ArXiv e-prints, 2017.
    Joint work with Julian Dibbelt, Thomas Pajor, and Dorothea Wagner.
    [ html ]
  5. Distributed Graph Clustering using Modularity and Map Equation.
    Technical report, arXiv, 2017.
    arXiv:1710.09605 [cs.DS].
    Joint work with Michael Hamann, Dorothea Wagner, and Tim Zeitz.
    [ html | pdf ]
  6. Intriguingly Simple and Efficient Time-Dependent Routing in Road Networks.
    Technical report, ArXiv e-prints, 2016.
    [ html ]
  7. Fast Quasi-Threshold Editing.
    Technical report, arXiv e-prints, 2015.
    Joint work with Ulrik Brandes, Michael Hamann, and Dorothea Wagner.
    [ html ]
  8. Fast Exact Shortest Path and Distance Queries on Road Networks with Parametrized Costs.
    Technical Report abs/1509.03165, ArXiv e-prints, 2015.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ html ]
  9. Graph Bisection with Pareto-Optimization.
    Technical report, ArXiv e-prints, 2015.
    Joint work with Michael Hamann.
    [ html ]
  10. Customizable Contraction Hierarchies.
    Technical report, ArXiv e-prints, 2014.
    Joint work with Julian Dibbelt and Dorothea Wagner.
    [ html ]