Institute of Theoretical Informatics, Algorithmics

Publications

Journal articles

  1. Search-space size in contraction hierarchies.
    Theoretical Computer Science, 645:112–127, 2016.
    Joint work with Tobias Columbus, Ignaz Rutter, and Dorothea Wagner.
  2. On the Complexity of Partitioning Graphs for Arc-Flags.
    Journal of Graph Algorithms and Applications, 17(3):265–299, 2013.
    Joint work with Moritz Baum, Ignaz Rutter, and Dorothea Wagner.
    [ html ]
  3. A Constraint Programming-Based Approach to a Large-Scale Energy Management Problem with Varied Constraints.
    Journal of Scheduling, 16(6):629–648, 2013.
    Joint work with Felix Brandt, Markus Völker, and Andreas Cardeneo.
    [ html ]
  4. The Shortcut Problem – Complexity and Algorithms.
    Journal of Graph Algorithms and Applications, 16(2):447–481, 2012.
    Joint work with Gianlorenzo D'Angelo, Daniel Delling, Andrea Schumm, and Dorothea Wagner.
    [ html ]
  5. Experimental Study on Speed-Up Techniques for Timetable Information Systems.
    Networks, 57(1):38–52, January 2011.
    Joint work with Daniel Delling and Dorothea Wagner.
    [ pdf ]
  6. 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 Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  7. 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 Daniel Delling.
    [ html | pdf ]

Conference articles

  1. Search-Space Size in Contraction Hierarchies.
    In: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming (ICALP'13), volume 7965 of Lecture Notes in Computer Science, pages 93–104. Springer, 2013.
    Joint work with Tobias Columbus, Ignaz Rutter, and Dorothea Wagner.
  2. On the Complexity of Partitioning Graphs for Arc-Flags.
    In: Proceedings of the 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'12), volume 25 of OpenAccess Series in Informatics (OASIcs), pages 71–82. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012.
    Joint work with Moritz Baum, Ignaz Rutter, and Dorothea Wagner.
    [ html | pdf ]
  3. Preprocessing Speed-Up Techniques is Hard.
    In: Proceedings of the 7th Conference on Algorithms and Complexity (CIAC'10), volume 6078 of Lecture Notes in Computer Science, pages 359–370. Springer, 2010.
    Joint work with Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner.
    [ pdf ]
  4. Synthetic Road Networks.
    In: Proceedings of the 6th International Conference on Algorithmic Aspects in Information and Management (AAIM'10), volume 6124 of Lecture Notes in Computer Science, pages 46–57. Springer, 2010.
    Joint work with Marcus Krug, Sascha Meinert, and Dorothea Wagner.
    [ html | pdf ]
  5. Enumerating and Generating Labeled k-Degenerate Graphs.
    In: Proceedings of the Seventh Workshop on Analytic Algorithmics and Combinatorics (ANALCO '10), pages 90–98. SIAM, 2010.
    Joint work with Marcus Krug and Dorothea Wagner.
  6. Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study.
    In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09), volume 5526 of Lecture Notes in Computer Science, pages 51–62. Springer, June 2009.
    Joint work with Dorothea Wagner.
    [ pdf ]
  7. 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 Gianlorenzo D'Angelo, Daniel Delling, and Dorothea Wagner.
    [ pdf ]
  8. 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 Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner.
    [ pdf ]
  9. 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 Daniel Delling.
    [ pdf ]
  10. 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 Daniel Delling and Dorothea Wagner.
    [ html | pdf ]

Dissertation

  1. Theory and Engineering for Shortest Paths and Delay Management.
    PhD thesis, Fakultät für Informatik, December 2010.
    [ html | pdf ]

Master's Thesis

  1. Dynamic Speed-Up Techniques for Dijkstra's Algorithm.
    Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, 2006.
    [ pdf ]

Technical reports

  1. Preprocessing Speed-Up Techniques is Hard.
    Technical Report 2010-04, ITI Wagner, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    Joint work with Tobias Columbus, Bastian Katz, Marcus Krug, and Dorothea Wagner.
    [ html ]
  2. The Shortcut Problem – Complexity and Algorithms.
    Technical Report 2010-17, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2010.
    Joint work with Gianlorenzo D'Angelo, Daniel Delling, Andrea Schumm, and Dorothea Wagner.
    [ html ]
  3. Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study.
    Technical Report 2009,6, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2009.
    Joint work with Dorothea Wagner.
    [ html | pdf ]
  4. Impact of Shortcuts on Speedup Techniques.
    Technical Report 2008-10, ITI Wagner, Faculty of Informatics, Universität Karlsruhe (TH), 2008.
    Joint work with Daniel Delling and Dorothea Wagner.
    [ pdf ]
  5. The Complexity of the Shortcut Problem.
    Technical Report 117, Arrival Technical Report, 2007.
    Joint work with Gianlorenzo D'Angelo, Daniel Delling, and Dorothea Wagner.
    [ pdf ]
  6. 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 Daniel Delling and Dorothea Wagner.
    [ html | pdf ]