Publications

The following is a list of my academic publications and patents. Journal articles, book chapters, and conference publications have all been peer-reviewed.

Journal Articles and Book Chapters

1. Energy-optimal routes for battery electric vehicles. By Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, Tobias Zündorf. Algorithmica, vol. 82(5), pp. 1490–1546, 2020.
   [abstract] [bibtex]

   @article{bdpswz-eorbev-20,
     author = {Baum, Moritz and Dibbelt, Julian and Pajor, Thomas and Sauer, Jonas and Wagner, Dorothea and Z{\"u}ndorf, Tobias},
     date-added = {2025-10-25 22:28:28 -0700},
     date-modified = {2025-10-25 22:29:09 -0700},
     journal = {Algorithmica},
     number = {5},
     pages = {1490--1546},
     publisher = {Springer},
     title = {Energy-optimal routes for battery electric vehicles},
     volume = {82},
     year = {2020}
   }
   

   We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by profiles, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra’s algorithm to compute energy-optimal paths or profiles. Further, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the whole network. This enables flexible updates due to, e.g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks.
2. A Robust and Scalable Algorithm for the Steiner Problem in Graphs. By Thomas Pajor, Eduardo Uchoa, Renato F. Werneck. Mathematical Programming Computation, vol. 10(1), pp. 69–118, 2018.
   [abstract] [publisher] [bibtex]

   @article{puw-rsaspg-18,
     author = {Pajor, Thomas and Uchoa, Eduardo and Werneck, Renato F.},
     date-added = {2019-02-03 22:13:51 -0800},
     date-modified = {2019-02-03 22:21:52 -0800},
     day = {01},
     doi = {10.1007/s12532-017-0123-4},
     issn = {1867-2957},
     journal = {Mathematical Programming Computation},
     month = mar,
     number = {1},
     pages = {69--118},
     title = {A Robust and Scalable Algorithm for the Steiner Problem in Graphs},
     url = {https://doi.org/10.1007/s12532-017-0123-4},
     volume = {10},
     year = {2018},
     bdsk-url-1 = {https://doi.org/10.1007/s12532-017-0123-4}
   }
   

   We present an effective heuristic for the Steiner Problem in Graphs. Its main elements are a multistart algorithm coupled with aggressive combination of elite solutions, both leveraging recently-proposed fast local searches. We also propose a fast implementation of a well-known dual ascent algorithm that not only makes our heuristics more robust (by dealing with easier cases quickly), but can also be used as a building block of an exact branch-and-bound algorithm that is quite effective for some inputs. On all graph classes we consider, our heuristic is competitive with (and sometimes more effective than) any previous approach with similar running times. It is also scalable: with long runs, we could improve or match the best published results for most open instances in the literature.
3. Connection Scan Algorithm. By Julian Dibbelt, Thomas Pajor, Ben Strasser, Dorothea Wagner. ACM Journal of Experimental Algorithmics, vol. 23(1), pp. 1.7:1–1.7:56, 2018.
   [abstract] [publisher] [bibtex]

   @article{dpsw-csa-18,
     author = {Dibbelt, Julian and Pajor, Thomas and Strasser, Ben and Wagner, Dorothea},
     date-added = {2019-02-03 22:03:43 -0800},
     date-modified = {2019-02-03 22:05:55 -0800},
     journal = {ACM Journal of Experimental Algorithmics},
     month = oct,
     number = {1},
     pages = {1.7:1--1.7:56},
     title = {Connection Scan Algorithm},
     url = {http://doi.acm.org/10.1145/3274661},
     volume = {23},
     year = {2018},
     bdsk-url-1 = {http://doi.acm.org/10.1145/3274661}
   }
   

   We introduce the Connection Scan Algorithm (CSA) to efficiently answer queries to timetable information systems. The input consists, in the simplest setting, of a source position and a desired target position. The output consists of a sequence of vehicles such as trains or buses that a traveler should take to get from the source to the target. We study several problem variations such as the earliest arrival and profile problems. We present algorithm variants that only optimize the arrival time or additionally optimize the number of transfers in the Pareto sense. An advantage of CSA is that it can easily adjust to changes in the timetable, allowing the easy incorporation of known vehicle delays. We additionally introduce the Minimum Expected Arrival Time (MEAT) problem to handle possible, uncertain, future vehicle delays. We present a solution to the MEAT problem that is based on CSA. Finally, we extend CSA using the multilevel overlay paradigm to answer complex queries on nationwide integrated timetables with trains and buses.
4. Route Planning in Transportation Networks. By Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck. In: Algorithm Engineering: Selected Results and Surveys. Springer International Publishing, Cham, pp. 19–80, 2016.
   [abstract] [publisher] [bibtex]

   @inbook{bdgmpsww-rptn-16,
     address = {Cham},
     author = {Bast, Hannah and Delling, Daniel and Goldberg, Andrew and M{\"u}ller-Hannemann, Matthias and Pajor, Thomas and Sanders, Peter and Wagner, Dorothea and Werneck, Renato F.},
     booktitle = {Algorithm Engineering: Selected Results and Surveys},
     date-added = {2018-01-20 16:52:30 +0000},
     date-modified = {2018-01-20 16:52:48 +0000},
     doi = {10.1007/978-3-319-49487-6_2},
     editor = {Kliemann, Lasse and Sanders, Peter},
     isbn = {978-3-319-49487-6},
     pages = {19--80},
     publisher = {Springer International Publishing},
     title = {Route Planning in Transportation Networks},
     url = {https://doi.org/10.1007/978-3-319-49487-6_2},
     year = {2016},
     bdsk-url-1 = {https://doi.org/10.1007/978-3-319-49487-6_2}
   }
   

   We survey recent advances in algorithms for route planning in transportation networks. For road networks, we show that one can compute driving directions in milliseconds or less even at continental scale. A variety of techniques provide different trade-offs between preprocessing effort, space requirements, and query time. Some algorithms can answer queries in a fraction of a microsecond, while others can deal efficiently with real-time traffic. Journey planning on public transportation systems, although conceptually similar, is a significantly harder problem due to its inherent time-dependent and multicriteria nature. Although exact algorithms are fast enough for interactive queries on metropolitan transit systems, dealing with continent-sized instances requires simplifications or heavy preprocessing. The multimodal route planning problem, which seeks journeys combining schedule-based transportation (buses, trains) with unrestricted modes (walking, driving), is even harder, relying on approximate solutions even for metropolitan inputs.
5. Customizable Route Planning in Road Networks. By Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck. Transportation Science, 2015.
   [abstract] [publisher] [bibtex]

   @article{dgpw-crprn-15,
     author = {Delling, Daniel and Goldberg, Andrew V. and Pajor, Thomas and Werneck, Renato F.},
     date-modified = {2015-08-15 17:47:12 +0000},
     doi = {10.1287/trsc.2014.0579},
     journal = {Transportation Science},
     title = {Customizable Route Planning in Road Networks},
     url = {http://dx.doi.org/10.1287/trsc.2014.0579},
     year = {2015},
     bdsk-url-1 = {http://research.microsoft.com/apps/pubs/?id=198358},
     bdsk-url-2 = {http://dx.doi.org/10.1287/trsc.2014.0579}
   }
   

   We propose the first routing engine for computing driving directions in large-scale road networks that satisfies all requirements of a real-world production system. It supports arbitrary metrics (cost functions) and turn costs, enables real-time queries, and can incorporate a new metric in less than a second, which is fast enough to support real-time traffic updates and personalized cost functions. The amount of metric-specific data is a small fraction of the graph itself, which allows us to maintain several metrics in memory simultaneously. The algorithm is the core of the routing engine currently in use by Bing Maps.
6. Round-Based Public Transit Routing. By Daniel Delling, Thomas Pajor, Renato F. Werneck. Transportation Science, vol. 49(3), pp. 591–604, 2014.
   [abstract] [publisher] [bibtex]

   @article{dpw-rbptr-14,
     annote = {doi: 10.1287/trsc.2014.0534},
     author = {Delling, Daniel and Pajor, Thomas and Werneck, Renato F.},
     booktitle = {Transportation Science},
     date = {2014/10/30},
     date-added = {2015-06-12 03:06:35 +0000},
     date-modified = {2015-07-17 16:23:49 +0000},
     doi = {10.1287/trsc.2014.0534},
     isbn = {0041-1655},
     journal = {Transportation Science},
     journal1 = {Transportation Science},
     m3 = {doi: 10.1287/trsc.2014.0534},
     n2 = {We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for multiple criteria, such as arrival time and number of transfers. Existing algorithms consider this as a graph problem and solve it using various graph search algorithms. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Starting from arrival time and number of transfers as criteria, it can be easily extended to handle flexible departure times or arbitrary additional criteria. As practical examples we consider fare zones and reliability of transfers. When run on complex public transportation networks (such as London), RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications.},
     number = {3},
     pages = {591--604},
     publisher = {INFORMS},
     title = {Round-Based Public Transit Routing},
     ty = {JOUR},
     url = {http://dx.doi.org/10.1287/trsc.2014.0534},
     volume = {49},
     year = {2015},
     year1 = {2014},
     bdsk-url-1 = {http://dx.doi.org/10.1287/trsc.2014.0534}
   }
   

   We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for multiple criteria, such as arrival time and number of transfers. Existing algorithms consider this as a graph problem and solve it using various graph search algorithms. Unfortunately, this leads to either high query times or suboptimal solutions. We take a different approach. We introduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization using multiple cores. Because it does not rely on preprocessing, RAPTOR works in fully dynamic scenarios. Starting from arrival time and number of transfers as criteria, it can be easily extended to handle flexible departure times or arbitrary additional criteria. As practical examples we consider fare zones and reliability of transfers. When run on complex public transportation networks (such as London), RAPTOR computes all Pareto-optimal journeys between two random locations an order of magnitude faster than previous approaches, which easily enables interactive applications.
7. User-Constrained Multimodal Route Planning. By Julian Dibbelt, Thomas Pajor, Dorothea Wagner. Journal of Experimental Algorithmics, vol. 19, pp. 3.2:1.1–3.2:1.19, 2015.
   [abstract] [publisher] [bibtex]

   @article{dpw-ucmmr-14,
     acmid = {2699886},
     address = {New York, NY, USA},
     articleno = {3.2},
     author = {Dibbelt, Julian and Pajor, Thomas and Wagner, Dorothea},
     date-added = {2015-06-12 03:04:13 +0000},
     date-modified = {2015-08-15 17:55:03 +0000},
     doi = {10.1145/2699886},
     issn = {1084-6654},
     issue_date = {February 2015},
     journal = {Journal of Experimental Algorithmics},
     keywords = {Shortest paths, contraction, multimodal, route planning},
     month = apr,
     numpages = {1.09},
     pages = {3.2:1.1--3.2:1.19},
     publisher = {ACM},
     title = {User-Constrained Multimodal Route Planning},
     url = {http://doi.acm.org/10.1145/2699886},
     volume = {19},
     year = {2015},
     bdsk-url-1 = {http://doi.acm.org/10.1145/2699886},
     bdsk-url-2 = {http://dx.doi.org/10.1145/2699886}
   }
   

   In the multi-modal route planning problem we are given multiple transportation networks (e. g., pedestrian, road, public transit) and ask for a best integrated journey between two points. The main challenge is that a seemingly optimal journey may have changes between networks that do not reflect the user’s modal preferences. In fact, quickly computing reasonable multi-modal routes remains a challenging problem: Previous approaches either suffer from poor query performance or their available choices of modal preferences during query time is limited. In this work we focus on computing exact multi-modal journeys that can be restricted by specifying arbitrary modal sequences at query time. For example, a user can say whether he wants to only use public transit, or also prefers to use a taxi or walking at the beginning or end of the journey; or if he has no restrictions at all. By carefully adapting node contraction, a common ingredient to many speedup techniques on road networks, we are able to compute point-to-point queries on a continental network combined of cars, railroads and flights several orders of magnitude faster than Dijkstra’s algorithm. Thereby, we require little space overhead and obtain fast preprocessing times.
8. On D-regular Schematization of Embedded Paths. By Daniel Delling, Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, Ignaz Rutter. Computational Geometry: Theory and Applications, vol. 47(3), pp. 381–406, 2014.
   [abstract] [publisher] [bibtex]

   @article{dgnpr-osep-13,
     acmid = {2561625},
     author = {Delling, Daniel and Gemsa, Andreas and N\"{o}llenburg, Martin and Pajor, Thomas and Rutter, Ignaz},
     date-added = {2015-06-12 03:08:58 +0000},
     date-modified = {2015-08-15 18:11:15 +0000},
     doi = {10.1016/j.comgeo.2013.10.002},
     issn = {0925-7721},
     issue_date = {April, 2014},
     journal = {Computational Geometry: Theory and Applications},
     keywords = {Dynamic programming, Graph drawing, Mixed integer linear programming, NP-hardness, Path schematization},
     month = apr,
     number = {3},
     numpages = {26},
     pages = {381--406},
     publisher = {Elsevier Science Publishers B. V.},
     title = {On D-regular Schematization of Embedded Paths},
     url = {http://dx.doi.org/10.1016/j.comgeo.2013.10.002},
     volume = {47},
     year = {2014},
     bdsk-url-1 = {http://dx.doi.org/10.1016/j.comgeo.2013.10.002}
   }
   

   Motivated by drawing route sketches, we consider the d-regular path schematization problem. For this problem we are given an embedded path P (e.g., a route in a road network) and a positive integer d. The goal is to find a d-schematized embedding of P in which the orthogonal order of all vertices in the input is preserved and in which every edge has a direction that is an integer multiple of (90/d) degrees. We show that deciding whether a path can be d-schematized is NP-complete for any positive integer d. Despite the NP-hardness of the problem we still want to be able to generate route sketches and thus need to solve the d-regular path schematization problem. We explore two different algorithmic approaches, both of which consider two additional quality constraints: We require that every edge is drawn with a user-specified minimum length and we want to maximize the number of edges that are drawn with their preferred direction. The first algorithmic approach restricts the input paths to be axis-monotone. We show that there exists a polynomial-time algorithm that solves the d-regular path schematization problem for this restricted class of embedded paths. We extend this approach by a heuristic such that it can handle arbitrary simple paths. However, for the second step we cannot guarantee that the orthogonal order of the input embedding is maintained. The second approach is a formulation of the d-regular path schematization problem as a mixed integer linear program. Finally, we give an experimental evaluation which shows that both approaches generate reasonable route sketches for real-world data.
9. Parallel Computation of Best Connections in Public Transportation Networks. By Daniel Delling, Bastian Katz, Thomas Pajor. Journal of Experimental Algorithmics, vol. 17, pp. 4.4:4.1–4.4:4.26, 2012.
   [abstract] [publisher] [bibtex]

   @article{dkp-pcbc-12,
     acmid = {2345678},
     address = {New York, NY, USA},
     articleno = {4.4},
     author = {Delling, Daniel and Katz, Bastian and Pajor, Thomas},
     date-added = {2015-06-12 03:13:10 +0000},
     date-modified = {2015-08-15 18:11:47 +0000},
     doi = {10.1145/2133803.2345678},
     issn = {1084-6654},
     issue_date = {2012},
     journal = {Journal of Experimental Algorithmics},
     keywords = {Shortest paths, profile queries, public transportation, route planning},
     month = oct,
     numpages = {1.16},
     pages = {4.4:4.1--4.4:4.26},
     publisher = {ACM},
     title = {Parallel Computation of Best Connections in Public Transportation Networks},
     url = {http://doi.acm.org/10.1145/2133803.2345678},
     volume = {17},
     year = {2012},
     bdsk-url-1 = {http://doi.acm.org/10.1145/2133803.2345678},
     bdsk-url-2 = {http://dx.doi.org/10.1145/2133803.2345678}
   }
   

   Exploiting parallelism in route planning algorithms is a challenging algorithmic problem with obvious applications in mobile navigation and timetable information systems. In this work, we present a novel algorithm for the one-to-all profile-search problem in public transportation networks. It answers the question for all fastest connections between a given station S and any other station at any time of the day in a single query. This algorithm allows for a very natural parallelization, yielding excellent speed-ups on standard multicore servers. Our approach exploits the facts that, first, time-dependent travel-time functions in such networks can be represented as a special class of piecewise linear functions and, second, only few connections from S are useful to travel far away. Introducing the connection-setting property, we are able to extend Dijkstra’s algorithm in a sound manner. Furthermore, we also accelerate station-to-station queries by preprocessing important connections within the public transportation network. As a result, we are able to compute all relevant connections between two random stations in a complete public transportation network of a big city (New York) on a standard multi-core server in real time.
10. Engineering Time-Expanded Graphs for Faster Timetable Information. By Daniel Delling, Thomas Pajor, Dorothea Wagner. In: Robust and Online Large-Scale Optimization. Springer Berlin Heidelberg, pp. 182–206, 2009.
    [abstract] [publisher] [bibtex]

    @incollection{dpw-etegf-09,
      author = {Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
      booktitle = {Robust and Online Large-Scale Optimization},
      date-added = {2015-06-12 03:16:16 +0000},
      date-modified = {2015-08-15 18:13:03 +0000},
      doi = {10.1007/978-3-642-05465-5_7},
      editor = {Ahuja, Ravindra K. and M{\"o}hring, Rolf H. and Zaroliagis, Christos D.},
      isbn = {978-3-642-05464-8},
      language = {English},
      pages = {182-206},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Engineering Time-Expanded Graphs for Faster Timetable Information},
      url = {http://dx.doi.org/10.1007/978-3-642-05465-5_7},
      volume = {5868},
      year = {2009},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-05465-5_7}
    }
    

    We present an extension of the well-known time-expanded approach for timetable information. By remodeling unimportant stations, we are able to obtain faster query times with less space consumption than the original model. Moreover, we show that our extensions harmonize well with speed-up techniques whose adaption to timetable networks is more challenging than one might expect.

In Conference Proceedings

1. Fast and Exact Public Transit Routing with Restricted Pareto Sets. By Daniel Delling, Julian Dibbelt, Thomas Pajor. In: Proceedings of the 21st Meeting on Algorithm Engineering and Experiments (ALENEX’19). SIAM, pp. 54–65, 2019.
   [abstract] [pdf] [bibtex]

   @inproceedings{ddp-feptr-19,
     author = {Delling, Daniel and Dibbelt, Julian and Pajor, Thomas},
     booktitle = {Proceedings of the 21st Meeting on Algorithm Engineering and Experiments (ALENEX'19)},
     date-added = {2019-02-03 21:54:38 -0800},
     date-modified = {2019-02-03 22:20:21 -0800},
     doi = {10.1137/1.9781611975499.5},
     month = jan,
     pages = {54--65},
     publisher = {SIAM},
     title = {Fast and Exact Public Transit Routing with Restricted Pareto Sets},
     year = {2019},
     bdsk-url-1 = {https://doi.org/10.1137/1.9781611975499.5}
   }
   

   We present a novel exact journey planning approach to computing a reasonable subset of multi-criteria Pareto sets in public transit networks. Our restriction is well defined and independent of the choice of algorithm. In order to compute the restricted Pareto set efficiently, we present Bounded McRAPTOR, a new set of algorithms that extend the well-known McRAPTOR algorithm. The fastest variant employs a novel pruning scheme based on carefully computed bounds. Experiments on large metropolitan networks show that a four-criteria restricted Pareto set can be computed faster by a factor of up to 65, while retaining the important journeys of the full Pareto set. This easily enables interactive applications in practice, making multi-criteria Pareto-optimal journey planning scalable without the need of a preprocessing-based speedup technique.
2. Faster Transit Routing by Hyper Partitioning. By Daniel Delling, Julian Dibbelt, Thomas Pajor, Tobias Zündorf. In: Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’17). pp. 8:1–8:14, 2017.
   [abstract] [pdf] [publisher] [bibtex]

   @inproceedings{ddpz-ftrhp-17,
     author = {Delling, Daniel and Dibbelt, Julian and Pajor, Thomas and Z{\"u}ndorf, Tobias},
     booktitle = {Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'17)},
     date-added = {2018-01-20 15:54:08 +0000},
     date-modified = {2018-01-20 15:54:44 +0000},
     key = {ATMOS'17},
     pages = {8:1--8:14},
     pdf = {http://drops.dagstuhl.de/opus/volltexte/2017/7896/pdf/OASIcs-ATMOS-2017-8.pdf},
     series = {OpenAccess Series in Informatics (OASIcs)},
     title = {Faster Transit Routing by Hyper Partitioning},
     url = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7896},
     volume = {59},
     year = {2017},
     bdsk-url-1 = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=7896}
   }
   

   We present a preprocessing-based acceleration technique for computing bi-criteria Pareto-optimal journeys in public transit networks, based on the well-known RAPTOR algorithm [Delling et al 2015]. Our key idea is to first partition a hypergraph into cells, in which vertices correspond to routes (e.g., bus lines) and hyperedges to stops, and to then mark routes sufficient for optimal travel across cells. The query can then be restricted to marked routes and those in the source and target cells. This results in a practical approach, suitable for networks that are too large to be efficiently handled by the basic RAPTOR algorithm.
3. Dynamic Time-Dependent Route Planning in Road Networks with User Preferences. By Moritz Baum, Julian Dibbelt, Thomas Pajor, Dorothea Wagner. In: Proceedings of the 15th International Symposium on Experimental Algorithms (SEA’16). Springer, pp. 33–49, 2016.
   [abstract] [publisher] [bibtex]

   @inproceedings{bdpw-dtdrp-16,
     author = {Baum, Moritz and Dibbelt, Julian and Pajor, Thomas and Wagner, Dorothea},
     booktitle = {Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16)},
     date-added = {2018-01-20 15:49:48 +0000},
     date-modified = {2018-01-20 15:50:30 +0000},
     key = {SEA'16},
     pages = {33--49},
     publisher = {Springer},
     series = {Lecture Notes in Computer Science},
     title = {{Dynamic Time-Dependent Route Planning in Road Networks with User Preferences}},
     url = {http://link.springer.com/chapter/10.1007/978-3-319-38851-9_3},
     volume = {9685},
     year = {2016},
     bdsk-url-1 = {http://link.springer.com/chapter/10.1007/978-3-319-38851-9_3}
   }
   

   Algorithms for computing driving directions on road networks often presume constant costs on each arc. In practice, the current traffic situation significantly influences the travel time. One can distinguish traffic congestion that can be predicted using historical traffic data, and congestion due to unpredictable events, e.g., accidents. We study the dynamic and time-dependent route planning problem, which takes both live traffic and long-term prediction into account. We propose a practical algorithm that, while robust to user preferences, is able to integrate global changes of the time-dependent metric faster than previous approaches and allows queries in the order of milliseconds.
4. Towards Realistic Pedestrian Route Planning. By Simeon Danailov Andreev, Julian Dibbelt, Martin Nöllenburg, Thomas Pajor, Dorothea Wagner. In: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’15). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2015.
   [pdf] [bibtex]

   @inproceedings{adnpw-trprp-15,
     address = {Dagstuhl, Germany},
     author = {Andreev, Simeon Danailov and Dibbelt, Julian and N{\"o}llenburg, Martin and Pajor, Thomas and Wagner, Dorothea},
     booktitle = {15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'15)},
     date-added = {2015-06-12 03:40:03 +0000},
     date-modified = {2015-08-15 00:33:19 +0000},
     month = sep,
     publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
     series = {OpenAccess Series in Informatics (OASIcs)},
     title = {Towards Realistic Pedestrian Route Planning},
     year = {2015}
   }
   

5. Public Transit Labeling. By Daniel Delling, Julian Dibbelt, Thomas Pajor, Renato F. Werneck. In: Proceedings of the 14th International Symposium on Experimental Algorithms (SEA’15). Springer International Publishing, pp. 273–285, 2015.
   [pdf] [publisher] [bibtex]

   @inproceedings{ddpw-ptl-15,
     author = {Delling, Daniel and Dibbelt, Julian and Pajor, Thomas and Werneck, Renato F.},
     booktitle = {Proceedings of the 14th International Symposium on Experimental Algorithms (SEA'15)},
     date-added = {2015-06-27 16:13:37 +0000},
     date-modified = {2015-08-15 00:31:57 +0000},
     doi = {10.1007/978-3-319-20086-6_21},
     editor = {Bampis, Evripidis},
     isbn = {978-3-319-20085-9},
     language = {English},
     month = jun,
     pages = {273-285},
     publisher = {Springer International Publishing},
     series = {Lecture Notes in Computer Science},
     title = {Public Transit Labeling},
     url = {http://dx.doi.org/10.1007/978-3-319-20086-6_21},
     volume = {9125},
     year = {2015},
     bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-319-20086-6_21}
   }
   

6. Better Transit Routing by Exploiting Vehicle GPS Data. By Daniel Delling, Giuseppe F. Italiano, Thomas Pajor, Federico Santaroni. In: Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science. ACM, New York, NY, USA, pp. 31–40, 2014.
   [pdf] [publisher] [bibtex]

   @inproceedings{dips-btrev-14,
     acmid = {2674923},
     address = {New York, NY, USA},
     author = {Delling, Daniel and Italiano, Giuseppe F. and Pajor, Thomas and Santaroni, Federico},
     booktitle = {Proceedings of the 7th {ACM SIGSPATIAL} International Workshop on Computational Transportation Science},
     date-added = {2015-06-12 03:25:54 +0000},
     date-modified = {2015-06-12 03:26:27 +0000},
     doi = {10.1145/2674918.2674923},
     isbn = {978-1-4503-3138-8},
     location = {Dallas/Fort Worth, Texas},
     numpages = {10},
     pages = {31--40},
     publisher = {ACM},
     series = {IWCTS '14},
     title = {Better Transit Routing by Exploiting Vehicle {GPS} Data},
     url = {http://doi.acm.org/10.1145/2674918.2674923},
     year = {2014},
     bdsk-url-1 = {http://doi.acm.org/10.1145/2674918.2674923},
     bdsk-url-2 = {http://dx.doi.org/10.1145/2674918.2674923}
   }
   

7. Computing Classic Closeness Centrality, at Scale. By Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck. In: Proceedings of the Second ACM Conference on Online Social Networks. ACM, New York, NY, USA, pp. 37–50, 2014.
   [pdf] [publisher] [bibtex]

   @inproceedings{cdpw-ccccs-14,
     acmid = {2660465},
     address = {New York, NY, USA},
     arxiv = {http://arxiv.org/abs/1409.0035},
     author = {Cohen, Edith and Delling, Daniel and Pajor, Thomas and Werneck, Renato F.},
     booktitle = {Proceedings of the Second {ACM} Conference on Online Social Networks},
     date-added = {2015-06-12 03:34:53 +0000},
     date-modified = {2015-06-21 17:46:47 +0000},
     doi = {10.1145/2660460.2660465},
     isbn = {978-1-4503-3198-2},
     keywords = {centrality, estimation, pivoting, sampling},
     location = {Dublin, Ireland},
     note = {Best Paper Award},
     numpages = {14},
     pages = {37--50},
     publisher = {ACM},
     series = {COSN '14},
     title = {Computing Classic Closeness Centrality, at Scale},
     url = {http://doi.acm.org/10.1145/2660460.2660465},
     year = {2014},
     bdsk-url-1 = {http://doi.acm.org/10.1145/2660460.2660465},
     bdsk-url-2 = {http://dx.doi.org/10.1145/2660460.2660465}
   }
   

8. Sketch-based Influence Maximization and Computation: Scaling Up with Guarantees. By Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck. In: Proceedings of the 23rd ACM International Conference on Information and Knowledge Management. ACM, New York, NY, USA, pp. 629–638, 2014.
   [pdf] [publisher] [bibtex]

   @inproceedings{cdpw-simcs-14,
     acmid = {2662077},
     address = {New York, NY, USA},
     arxiv = {http://arxiv.org/abs/1408.6282},
     author = {Cohen, Edith and Delling, Daniel and Pajor, Thomas and Werneck, Renato F.},
     booktitle = {Proceedings of the 23rd {ACM} International Conference on Information and Knowledge Management},
     date-added = {2015-06-12 03:37:59 +0000},
     date-modified = {2015-06-21 17:47:14 +0000},
     doi = {10.1145/2661829.2662077},
     isbn = {978-1-4503-2598-1},
     keywords = {algorithms, estimation, experimentation, theory},
     location = {Shanghai, China},
     numpages = {10},
     pages = {629--638},
     publisher = {ACM},
     series = {CIKM '14},
     title = {Sketch-based Influence Maximization and Computation: Scaling Up with Guarantees},
     url = {http://doi.acm.org/10.1145/2661829.2662077},
     year = {2014},
     bdsk-url-1 = {http://doi.acm.org/10.1145/2661829.2662077},
     bdsk-url-2 = {http://dx.doi.org/10.1145/2661829.2662077}
   }
   

9. Speed-Consumption Tradeoff for Electric Vehicle Route Planning. By Moritz Baum, Julian Dibbelt, Lorenz Hübschle-Schneider, Thomas Pajor, Dorothea Wagner. In: Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’14). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 138–151, 2014.
   [abstract] [pdf] [publisher] [bibtex]

   @inproceedings{bdhpw-sctev-14,
     author = {Baum, Moritz and Dibbelt, Julian and H{\"u}bschle-Schneider, Lorenz and Pajor, Thomas and Wagner, Dorothea},
     booktitle = {Proceedings of the 14th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'14)},
     date-added = {2018-01-20 16:59:07 +0000},
     date-modified = {2018-01-20 16:59:53 +0000},
     editor = {Funke, Stefan and Mihal{\'a}k, Mat{\'u}{\v s}},
     key = {ATMOS'14},
     pages = {138--151},
     pdf = {http://i11www.kit.edu/extra/publications/bdhpw-sctev-14.pdf},
     publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik},
     series = {OpenAccess Series in Informatics (OASIcs)},
     title = {Speed-Consumption Tradeoff for Electric Vehicle Route Planning},
     url = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=4758},
     volume = {42},
     year = {2014},
     bdsk-url-1 = {http://drops.dagstuhl.de/opus/frontdoor.php?source_opus=4758}
   }
   

   We study the problem of computing routes for electric vehicles (EVs) in road networks. Since their battery capacity is limited, and consumed energy per distance increases with velocity, driving the fastest route is often not desirable and may even be infeasible. On the other hand, the energy-optimal route may be too conservative in that it contains unnecessary detours or simply takes too long. In this work, we propose to use multicriteria optimization to obtain Pareto sets of routes that trade energy consumption for speed. In particular, we exploit the fact that the same road segment can be driven at different speeds within reasonable intervals. As a result, we are able to provide routes with low energy consumption that still follow major roads, such as freeways. Unfortunately, the size of the resulting Pareto sets can be too large to be practical. We therefore also propose several nontrivial techniques that can be applied on-line at query time in order to speed up computation and filter insignificant solutions from the Pareto sets. Our extensive experimental study, which uses a real-world energy consumption model, reveals that we are able to compute diverse sets of alternative routes on continental networks that closely resemble the exact Pareto set in just under a second—several orders of magnitude faster than the exhaustive algorithm.
10. Robust Distance Queries on Massive Networks. By Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck. In: Proceedings of the 22nd Annual European Symposium on Algorithms (ESA’14). Springer Berlin Heidelberg, pp. 321–333, 2014.
    [pdf] [publisher] [bibtex]

    @inproceedings{dgpw-rdqmn-14,
      author = {Delling, Daniel and Goldberg, Andrew V. and Pajor, Thomas and Werneck, Renato F.},
      booktitle = {Proceedings of the 22nd Annual European Symposium on Algorithms ({ESA'14})},
      date-added = {2015-06-12 03:28:22 +0000},
      date-modified = {2015-06-12 15:18:24 +0000},
      doi = {10.1007/978-3-662-44777-2_27},
      editor = {Schulz, Andreas S. and Wagner, Dorothea},
      isbn = {978-3-662-44776-5},
      language = {English},
      pages = {321-333},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Robust Distance Queries on Massive Networks},
      url = {http://dx.doi.org/10.1007/978-3-662-44777-2_27},
      volume = {8737},
      year = {2014},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-662-44777-2_27}
    }
    

11. Energy-optimal Routes for Electric Vehicles. By Moritz Baum, Julian Dibbelt, Thomas Pajor, Dorothea Wagner. In: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. ACM, New York, NY, USA, pp. 54–63, 2013.
    [pdf] [publisher] [bibtex]

    @inproceedings{bdpw-eorev-13,
      acmid = {2525361},
      address = {New York, NY, USA},
      author = {Baum, Moritz and Dibbelt, Julian and Pajor, Thomas and Wagner, Dorothea},
      booktitle = {Proceedings of the 21st {ACM SIGSPATIAL} International Conference on Advances in Geographic Information Systems},
      date-added = {2015-06-12 03:45:03 +0000},
      date-modified = {2015-06-12 03:45:36 +0000},
      doi = {10.1145/2525314.2525361},
      isbn = {978-1-4503-2521-9},
      keywords = {electric vehicles, energy consumption, road networks, route planning, shortest paths, speedup technique},
      location = {Orlando, Florida},
      numpages = {10},
      pages = {54--63},
      publisher = {ACM},
      series = {SIGSPATIAL'13},
      title = {Energy-optimal Routes for Electric Vehicles},
      url = {http://doi.acm.org/10.1145/2525314.2525361},
      year = {2013},
      bdsk-url-1 = {http://doi.acm.org/10.1145/2525314.2525361},
      bdsk-url-2 = {http://dx.doi.org/10.1145/2525314.2525361}
    }
    

12. Intriguingly Simple and Fast Transit Routing. By Julian Dibbelt, Thomas Pajor, Ben Strasser, Dorothea Wagner. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13). Springer Berlin Heidelberg, pp. 43–54, 2013.
    [pdf] [publisher] [bibtex]

    @inproceedings{dpsw-isftr-13,
      author = {Dibbelt, Julian and Pajor, Thomas and Strasser, Ben and Wagner, Dorothea},
      booktitle = {Proceedings of the 12th International Symposium on Experimental Algorithms ({SEA'13})},
      date-modified = {2015-08-14 21:47:43 +0000},
      doi = {10.1007/978-3-642-38527-8_6},
      editor = {Bonifaci, Vincenzo and Demetrescu, Camil and Marchetti-Spaccamela, Alberto},
      isbn = {978-3-642-38526-1},
      pages = {43--54},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Intriguingly Simple and Fast Transit Routing},
      url = {http://dx.doi.org/10.1007/978-3-642-38527-8_6},
      volume = {7933},
      year = {2013},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-38527-8_6}
    }
    

13. Efficient Computation of Jogging Routes. By Andreas Gemsa, Thomas Pajor, Dorothea Wagner, Tobias Zündorf. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13). Springer Berlin Heidelberg, pp. 272–283, 2013.
    [pdf] [publisher] [bibtex]

    @inproceedings{gpwz-ecjr-13,
      author = {Gemsa, Andreas and Pajor, Thomas and Wagner, Dorothea and Z{\"u}ndorf, Tobias},
      booktitle = {Proceedings of the 12th International Symposium on Experimental Algorithms ({SEA'13})},
      date-modified = {2015-08-14 21:47:31 +0000},
      doi = {10.1007/978-3-642-38527-8_25},
      editor = {Bonifaci, Vincenzo and Demetrescu, Camil and Marchetti-Spaccamela, Alberto},
      pages = {272--283},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Efficient Computation of Jogging Routes},
      url = {http://dx.doi.org/10.1007/978-3-642-38527-8_25},
      volume = {7933},
      year = {2013},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-38527-8_25}
    }
    

14. Computing Multimodal Journeys in Practice. By Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, Renato F. Werneck. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA’13). Springer, pp. 260–271, 2013.
    [pdf] [bibtex]

    @inproceedings{ddpww-cmjp-13,
      author = {Delling, Daniel and Dibbelt, Julian and Pajor, Thomas and Wagner, Dorothea and Werneck, Renato F.},
      booktitle = {Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)},
      date-modified = {2015-08-14 21:47:10 +0000},
      doi = {10.1007/978-3-642-38527-8_24},
      pages = {260--271},
      publisher = {Springer},
      series = {Lecture Notes in Computer Science},
      title = {Computing Multimodal Journeys in Practice},
      volume = {7933},
      year = {2013},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-38527-8_24}
    }
    

15. User-Constrained Multi-Modal Route Planning. By Julian Dibbelt, Thomas Pajor, Dorothea Wagner. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12). SIAM, pp. 118–129, 2012.
    [pdf] [bibtex]

    @inproceedings{dpw-ucmmr-12,
      author = {Dibbelt, Julian and Pajor, Thomas and Wagner, Dorothea},
      booktitle = {Proceedings of the 14th Meeting on Algorithm Engineering and Experiments ({ALENEX'12})},
      date-modified = {2015-08-14 21:48:20 +0000},
      doi = {10.1137/1.9781611972924.12},
      pages = {118--129},
      publisher = {SIAM},
      title = {User-Constrained Multi-Modal Route Planning},
      year = {2012},
      bdsk-url-1 = {http://dx.doi.org/10.1137/1.9781611972924.12}
    }
    

16. Round-Based Public Transit Routing. By Daniel Delling, Thomas Pajor, Renato F. Werneck. In: Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX’12). SIAM, pp. 130–140, 2012.
    [pdf] [bibtex]

    @inproceedings{dpw-rbptr-12,
      author = {Delling, Daniel and Pajor, Thomas and Werneck, Renato F.},
      booktitle = {Proceedings of the 14th Meeting on Algorithm Engineering and Experiments ({ALENEX'12})},
      date-modified = {2015-08-14 21:48:31 +0000},
      doi = {10.1137/1.9781611972924.13},
      pages = {130--140},
      publisher = {SIAM},
      title = {Round-Based Public Transit Routing},
      year = {2012},
      bdsk-url-1 = {http://siam.omnibooksonline.com/2012ALENEX/data/papers/024.pdf},
      bdsk-url-2 = {http://dx.doi.org/10.1137/1.9781611972924.13}
    }
    

17. Automatic Generation of Route Sketches. By Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, Ignaz Rutter. In: Proceedings of the 18th International Symposium on Graph Drawing (GD’10). Springer Berlin Heidelberg, pp. 391–392, 2011.
    [pdf] [publisher] [bibtex]

    @inproceedings{gnpr-agrs-10,
      author = {Gemsa, Andreas and N{\"o}llenburg, Martin and Pajor, Thomas and Rutter, Ignaz},
      booktitle = {Proceedings of the 18th International Symposium on Graph Drawing ({GD'10})},
      date-added = {2015-06-12 04:04:53 +0000},
      date-modified = {2015-06-12 04:05:19 +0000},
      doi = {10.1007/978-3-642-18469-7_37},
      editor = {Brandes, Ulrik and Cornelsen, Sabine},
      isbn = {978-3-642-18468-0},
      language = {English},
      pages = {391-392},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Automatic Generation of Route Sketches},
      url = {http://dx.doi.org/10.1007/978-3-642-18469-7_37},
      volume = {6502},
      year = {2011},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-18469-7_37}
    }
    

18. Customizable Route Planning. By Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck. In: Proceedings of the 10th International Symposium on Experimental Algorithms (SEA’11). Springer Berlin Heidelberg, pp. 376–387, 2011.
    [pdf] [publisher] [bibtex]

    @inproceedings{dgpw-crp-11,
      author = {Delling, Daniel and Goldberg, Andrew V. and Pajor, Thomas and Werneck, Renato F.},
      booktitle = {Proceedings of the 10th International Symposium on Experimental Algorithms ({SEA'11})},
      date-added = {2015-06-12 04:06:38 +0000},
      date-modified = {2015-06-12 04:06:42 +0000},
      doi = {10.1007/978-3-642-20662-7_32},
      editor = {Pardalos, Panos M. and Rebennack, Steffen},
      isbn = {978-3-642-20661-0},
      language = {English},
      pages = {376-387},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Customizable Route Planning},
      url = {http://dx.doi.org/10.1007/978-3-642-20662-7_32},
      volume = {6630},
      year = {2011},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-20662-7_32}
    }
    

19. UniALT for regular language contrained shortest paths on a multi-modal transportation network. By Dominik Kirchler, Leo Liberti, Thomas Pajor, Roberto Wolfler Calvo. In: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’11). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 64–75, 2011.
    [pdf] [publisher] [bibtex]

    @inproceedings{klpc-ualt-11,
      address = {Dagstuhl, Germany},
      annote = {Keywords: time-dependency, ALT, regular language, shortest path, multi-modal},
      author = {Kirchler, Dominik and Liberti, Leo and Pajor, Thomas and Calvo, Roberto Wolfler},
      booktitle = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems ({ATMOS'11})},
      date-added = {2015-06-12 04:10:28 +0000},
      date-modified = {2015-06-12 04:11:04 +0000},
      doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2011.64},
      editor = {Caprara, Alberto and Kontogiannis, Spyros},
      isbn = {978-3-939897-33-0},
      issn = {2190-6807},
      pages = {64--75},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
      series = {OpenAccess Series in Informatics (OASIcs)},
      title = {{UniALT} for regular language contrained shortest paths on a multi-modal transportation network},
      url = {http://drops.dagstuhl.de/opus/volltexte/2011/3267},
      urn = {urn:nbn:de:0030-drops-32670},
      volume = {20},
      year = {2011},
      bdsk-url-1 = {http://drops.dagstuhl.de/opus/volltexte/2011/3267},
      bdsk-url-2 = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2011.64}
    }
    

20. On d-Regular Schematization of Embedded Paths. By Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, Ignaz Rutter. In: SOFSEM 2011: Theory and Practice of Computer Science. Springer Berlin Heidelberg, pp. 260–271, 2011.
    [pdf] [publisher] [bibtex]

    @inproceedings{gnpr-osep-11,
      author = {Gemsa, Andreas and N{\"o}llenburg, Martin and Pajor, Thomas and Rutter, Ignaz},
      booktitle = {{SOFSEM} 2011: Theory and Practice of Computer Science},
      date-added = {2015-06-12 04:02:26 +0000},
      date-modified = {2015-06-12 04:03:01 +0000},
      doi = {10.1007/978-3-642-18381-2_22},
      editor = {{\v C}ern{\'a}, Ivana and Gyim{\'o}thy, Tibor and Hromkovi{\v c}, Juraj and Jefferey, Keith and Kr{\'a}lovi{\'c}, Rastislav and Vukoli{\'c}, Marko and Wolf, Stefan},
      isbn = {978-3-642-18380-5},
      language = {English},
      pages = {260-271},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {On d-Regular Schematization of Embedded Paths},
      url = {http://dx.doi.org/10.1007/978-3-642-18381-2_22},
      volume = {6543},
      year = {2011},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-18381-2_22}
    }
    

21. Parallel Computation of Best Connections in Public Transportation Networks. By Daniel Delling, Bastian Katz, Thomas Pajor. In: 24th International Parallel and Distributed Processing Symposium (IPDPS’10). IEEE Computer Society, pp. 1–12, 2010.
    [pdf] [bibtex]

    @inproceedings{dkp-pcbcp-10,
      author = {Delling, Daniel and Katz, Bastian and Pajor, Thomas},
      booktitle = {24th International Parallel and Distributed Processing Symposium ({IPDPS'10})},
      date-modified = {2015-08-14 21:48:02 +0000},
      doi = {10.1109/IPDPS.2010.5470345},
      pages = {1--12},
      publisher = {IEEE Computer Society},
      title = {Parallel Computation of Best Connections in Public Transportation Networks},
      year = {2010},
      bdsk-url-1 = {http://dx.doi.org/10.1109/IPDPS.2010.5470345}
    }
    

22. Path Schematization for Route Sketches. By Daniel Delling, Andreas Gemsa, Martin Nöllenburg, Thomas Pajor. In: Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT’10). Springer Berlin Heidelberg, pp. 285–296, 2010.
    [pdf] [publisher] [bibtex]

    @inproceedings{dgnp-psrs-10,
      author = {Delling, Daniel and Gemsa, Andreas and N{\"o}llenburg, Martin and Pajor, Thomas},
      booktitle = {Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory ({SWAT'10})},
      date-added = {2015-06-12 04:13:04 +0000},
      date-modified = {2015-06-12 04:13:04 +0000},
      doi = {10.1007/978-3-642-13731-0_27},
      editor = {Kaplan, Haim},
      isbn = {978-3-642-13730-3},
      language = {English},
      pages = {285-296},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Path Schematization for Route Sketches},
      url = {http://dx.doi.org/10.1007/978-3-642-13731-0_27},
      volume = {6139},
      year = {2010},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-13731-0_27}
    }
    

23. Accelerating Multi-modal Route Planning by Access-Nodes. By Daniel Delling, Thomas Pajor, Dorothea Wagner. In: Proceedings of the 17th Annual European Symposium on Algorithms (ESA’09). Springer Berlin Heidelberg, pp. 587–598, 2009.
    [pdf] [publisher] [bibtex]

    @inproceedings{dpw-ammrp-09,
      author = {Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
      booktitle = {Proceedings of the 17th Annual European Symposium on Algorithms ({ESA'09})},
      date-added = {2015-06-12 04:22:22 +0000},
      date-modified = {2015-06-12 04:22:22 +0000},
      doi = {10.1007/978-3-642-04128-0_53},
      editor = {Fiat, Amos and Sanders, Peter},
      isbn = {978-3-642-04127-3},
      language = {English},
      pages = {587-598},
      publisher = {Springer Berlin Heidelberg},
      series = {Lecture Notes in Computer Science},
      title = {Accelerating Multi-modal Route Planning by Access-Nodes},
      url = {http://dx.doi.org/10.1007/978-3-642-04128-0_53},
      volume = {5757},
      year = {2009},
      bdsk-url-1 = {http://dx.doi.org/10.1007/978-3-642-04128-0_53}
    }
    

24. Efficient Route Planning in Flight Networks. By Daniel Delling, Thomas Pajor, Dorothea Wagner, Christos Zaroliagis. In: 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’09). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2009.
    [pdf] [publisher] [bibtex]

    @inproceedings{dpwz-erpfn-09,
      address = {Dagstuhl, Germany},
      annote = {Keywords: Timetable information, flight modeling, shortest paths, multi criteria, table lookups},
      author = {Delling, Daniel and Pajor, Thomas and Wagner, Dorothea and Zaroliagis, Christos},
      booktitle = {9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems ({ATMOS'09})},
      date-added = {2015-06-12 04:23:40 +0000},
      date-modified = {2015-06-12 04:24:00 +0000},
      doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2009.2145},
      editor = {Clausen, Jens and Stefano, Gabriele Di},
      isbn = {978-3-939897-11-8},
      issn = {2190-6807},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      series = {OpenAccess Series in Informatics (OASIcs)},
      title = {Efficient Route Planning in Flight Networks},
      url = {http://drops.dagstuhl.de/opus/volltexte/2009/2145},
      urn = {urn:nbn:de:0030-drops-21450},
      volume = {12},
      year = {2009},
      bdsk-url-1 = {http://drops.dagstuhl.de/opus/volltexte/2009/2145},
      bdsk-url-2 = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2009.2145}
    }
    

25. Engineering Time-Expanded Graphs for Faster Timetable Information. By Daniel Delling, Thomas Pajor, Dorothea Wagner. In: 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS’08). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2008.
    [pdf] [publisher] [bibtex]

    @inproceedings{dpw-etegf-08,
      address = {Dagstuhl, Germany},
      annote = {Keywords: Timetable information, shortest path, modeling},
      author = {Delling, Daniel and Pajor, Thomas and Wagner, Dorothea},
      booktitle = {8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems ({ATMOS'08})},
      date-added = {2015-06-12 04:24:27 +0000},
      date-modified = {2015-06-12 04:24:46 +0000},
      doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1582},
      editor = {Fischetti, Matteo and Widmayer, Peter},
      isbn = {978-3-939897-07-1},
      issn = {2190-6807},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      series = {OpenAccess Series in Informatics (OASIcs)},
      title = {Engineering Time-Expanded Graphs for Faster Timetable Information},
      url = {http://drops.dagstuhl.de/opus/volltexte/2008/1582},
      urn = {urn:nbn:de:0030-drops-15826},
      volume = {9},
      year = {2008},
      bdsk-url-1 = {http://drops.dagstuhl.de/opus/volltexte/2008/1582},
      bdsk-url-2 = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1582}
    }
    

Technical Reports

1. Route Planning in Transportation Networks. By Hannah Bast, Daniel Delling, Andrew V. Goldberg, Matthias Müller–Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, Renato F. Werneck. Technical report abs/1504.05140, arXiv e-prints, 2015.
   [pdf] [publisher] [bibtex]

   @techreport{bdgmpsww-rptn-14,
     arxiv = {http://arxiv.org/abs/1504.05140},
     author = {Bast, Hannah and Delling, Daniel and Goldberg, Andrew V. and {M{\"u}ller--Hannemann}, Matthias and Pajor, Thomas and Sanders, Peter and Wagner, Dorothea and Werneck, Renato F.},
     date-modified = {2015-06-21 17:49:15 +0000},
     institution = {arXiv e-prints},
     number = {abs/1504.05140},
     pdf = {http://arxiv.org/pdf/1504.05140.pdf},
     title = {Route Planning in Transportation Networks},
     url = {http://arxiv.org/abs/1504.05140},
     year = {2015},
     bdsk-url-1 = {http://arxiv.org/abs/1504.05140}
   }
   

2. Timed Influence: Computation and Maximization. By Edith Cohen, Daniel Delling, Thomas Pajor, Renato F. Werneck. Technical report abs/1410.6976, arXiv e-prints, 2014.
   [pdf] [publisher] [bibtex]

   @techreport{cdpw-ticm-14,
     arxiv = {http://arxiv.org/abs/1410.6976},
     author = {Cohen, Edith and Delling, Daniel and Pajor, Thomas and Werneck, Renato F.},
     bibsource = {dblp computer science bibliography, http://dblp.org},
     biburl = {http://dblp.uni-trier.de/rec/bib/journals/corr/CohenDPW14b},
     date-added = {2015-06-12 04:27:30 +0000},
     date-modified = {2015-06-21 17:49:55 +0000},
     institution = {arXiv e-prints},
     number = {abs/1410.6976},
     pdf = {http://arxiv.org/pdf/1410.6976v3},
     title = {Timed Influence: Computation and Maximization},
     url = {http://arxiv.org/abs/1410.6976},
     year = {2014},
     bdsk-url-1 = {http://arxiv.org/abs/1410.6976}
   }
   

Theses

1. Algorithm Engineering for Realistic Journey Planning in Transportation Networks. By Thomas Pajor. PhD thesis, Department of Informatics, Karlsruhe Institute of Technology (KIT), 2013.
   [pdf] [publisher] [bibtex]

   @phdthesis{p-aerjp-13,
     author = {Pajor, Thomas},
     date-modified = {2015-08-14 20:43:29 +0000},
     institution = {Department of Informatics},
     month = nov,
     pdf = {https://publikationen.bibliothek.kit.edu/1000042955/3196166},
     school = {Karlsruhe Institute of Technology (KIT)},
     title = {Algorithm Engineering for Realistic Journey Planning in Transportation Networks},
     url = {https://publikationen.bibliothek.kit.edu/1000042955},
     year = {2013},
     bdsk-url-1 = {https://publikationen.bibliothek.kit.edu/1000042955}
   }
   

2. Multi-Modal Route Planning. By Thomas Pajor. Master's thesis, Fakultät für Informatik, Universität Karlsruhe (TH), 2009.
   [pdf] [bibtex]

   @mastersthesis{p-mmrp-09,
     author = {Pajor, Thomas},
     date-modified = {2015-06-12 04:49:26 +0000},
     institution = {Fakult{\"a}t f{\"u}r Informatik},
     month = mar,
     school = {Universit{\"a}t Karlsruhe (TH)},
     title = {Multi-Modal Route Planning},
     year = {2009},
     bdsk-url-1 = {http://i11www.kit.edu/extra/publications/p-mmrp-09.pdf}
   }
   

3. Goal Directed Speed-Up Techniques for Shortest Path Queries in Timetable Networks. By Thomas Pajor. Student Research Project, Fakultät für Informatik, Universität Karlsruhe (TH), 2008.
   [pdf] [bibtex]

   @misc{p-sutsp-08,
     author = {Pajor, Thomas},
     date-modified = {2015-08-14 20:43:05 +0000},
     institution = {Fakult{\"a}t f{\"u}r Informatik},
     month = jan,
     note = {Student Research Project},
     pdf = {http://i11www.kit.edu/extra/publications/p-sutsp-08.pdf},
     school = {Universit{\"a}t Karlsruhe (TH)},
     title = {Goal Directed Speed-Up Techniques for Shortest Path Queries in Timetable Networks},
     year = {2008}
   }
   

Patents

1. Presenting Transit Alight Notifications. By Brian J Andrich, Sara E Marcus, Thomas Pajor, Nick Provenzano, Tim A. Aerts, Alex Benevento, Leo Emile Jean Pierre Vallet, Samantha J. Bennett, Sara A. Bergquist, Nathan L. Fillhardt, Yun Jae Kim, Scott G. Jackson, Jan F. Sanchez Dudus, Ishan Bhutani, Ray R. Chen, Christopher Y. Tremblay. 2024.
   [publisher] [bibtex]

   @patent{pajor2022alight,
     author = {Andrich, Brian J and Marcus, Sara E and Pajor, Thomas and Provenzano, Nick and Aerts, Tim A. and Benevento, Alex and Vallet, Leo Emile Jean Pierre and Bennett, Samantha J. and Bergquist, Sara A. and Fillhardt, Nathan L. and Kim, Yun Jae and Jackson, Scott G. and Dudus, Jan F. Sanchez and Bhutani, Ishan and Chen, Ray R. and Tremblay, Christopher Y.},
     date-added = {2025-10-24 21:15:22 -0700},
     date-modified = {2025-10-24 21:21:59 -0700},
     month = dec,
     note = {US Patent 20220390242A1},
     publisher = {Google Patents},
     title = {Presenting Transit Alight Notifications},
     url = {https://patents.google.com/patent/EP4352461A1},
     year = {2024}
   }
   

2. Distance queries on massive networks. By Thomas Pajor, Daniel Delling, Renato F Werneck, Andrew V Goldberg. 2017.
   [publisher] [bibtex]

   @patent{pajor2017distance,
     author = {Pajor, Thomas and Delling, Daniel and Werneck, Renato F and Goldberg, Andrew V},
     date-added = {2021-04-11 12:31:33 +0100},
     date-modified = {2021-04-11 12:31:33 +0100},
     month = feb,
     note = {US Patent 9,576,073},
     publisher = {Google Patents},
     url = {https://patents.google.com/patent/US9576073B2},
     title = {Distance queries on massive networks},
     year = {2017}
   }
   

3. Estimating influence using sketches. By Renato F Werneck, Daniel Delling, Thomas Pajor, Edith Cohen. 2016.
   [publisher] [bibtex]

   @patent{werneck2016estimating,
     author = {Werneck, Renato F and Delling, Daniel and Pajor, Thomas and Cohen, Edith},
     month = sep,
     note = {US Patent 9,443,034},
     publisher = {Google Patents},
     url = {https://patents.google.com/patent/US9443034B2},
     title = {Estimating influence using sketches},
     year = {2016}
   }
   

4. Journey planning in public transportation networks. By Daniel Delling, Andrew Goldberg, Thomas Pajor, Renato Werneck. 2013.
   [publisher] [bibtex]

   @patent{delling2013journey,
     author = {Delling, Daniel and Goldberg, Andrew and Pajor, Thomas and Werneck, Renato},
     date-added = {2015-01-26 02:54:59 +0000},
     date-modified = {2015-01-26 02:55:22 +0000},
     month = jul,
     note = {US Patent 8,494,771},
     publisher = {Google Patents},
     title = {Journey planning in public transportation networks},
     url = {https://www.google.com/patents/US8494771},
     year = {2013},
     bdsk-url-1 = {https://www.google.com/patents/US8494771}
   }
   

5. Customizable route planning. By Daniel Delling, Renato Werneck, Andrew Goldberg, Thomas Pajor. 2012.
   [publisher] [bibtex]

   @patent{delling2012customizable,
     author = {Delling, Daniel and Werneck, Renato and Goldberg, Andrew and Pajor, Thomas},
     date-added = {2015-01-26 02:49:49 +0000},
     date-modified = {2015-01-26 02:53:16 +0000},
     month = dec,
     note = {US Patent App. 13/152,313},
     publisher = {Google Patents},
     title = {Customizable route planning},
     url = {https://www.google.com/patents/US20120310523},
     year = {2012},
     bdsk-url-1 = {https://www.google.com/patents/US20120310523}
   }