@misc{BeisegelChiarelliKoehleretal., author = {Beisegel, Jesse and Chiarelli, Nina and K{\"o}hler, Ekkehard and Krnc, Matjaž and Milanič, Martin and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Edge Elimination and Weighted Graph Classes}, series = {Graph-Theoretic Concepts in Computer Science - 46th International Workshop, {WG} 2020, Leeds, UK, June 24-26, 2020}, journal = {Graph-Theoretic Concepts in Computer Science - 46th International Workshop, {WG} 2020, Leeds, UK, June 24-26, 2020}, editor = {Adler, Isolde and M{\"u}ller, Haiko}, publisher = {Springer}, address = {Cham}, isbn = {978-3-030-60439-4}, issn = {1611-3349}, doi = {10.1007/978-3-030-60440-0_11}, pages = {134 -- 147}, language = {en} } @inproceedings{StrehlerDressler, author = {Strehler, Martin and Dressler, Daniel}, title = {Capacitated Confluent Flows: Complexity and Algorithms}, series = {Algorithms and Complexity, 7th International Conference, CIAC 2010, Rome, 2010}, booktitle = {Algorithms and Complexity, 7th International Conference, CIAC 2010, Rome, 2010}, publisher = {Berlin}, address = {Springer}, isbn = {978-3-642-13073-1}, pages = {347 -- 358}, language = {en} } @inproceedings{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Traffic signal optimization using cyclically expanded networks}, series = {10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10), September 9, 2010, Liverpool, United Kingdom}, booktitle = {10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10), September 9, 2010, Liverpool, United Kingdom}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-939897-20-0}, pages = {114 -- 129}, language = {en} } @inproceedings{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Signalanlagenoptimierung mit zyklisch expandierten Netzwerken}, series = {Optimierung in Verkehr und Transport, 16./17. 03. 2011, Stuttgart, Tagungsband Heureka '11}, booktitle = {Optimierung in Verkehr und Transport, 16./17. 03. 2011, Stuttgart, Tagungsband Heureka '11}, publisher = {FGSV-Verlag}, address = {K{\"o}ln}, isbn = {978-3-941790-72-8}, pages = {314 -- 333}, language = {de} } @misc{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Combining Static and Dynamic Models for Traffic Signal Optimization Inherent Load-dependent Travel Times in a Cyclically Time-expanded Network Model}, series = {Procedia - Social and Behavioral Science}, volume = {54}, journal = {Procedia - Social and Behavioral Science}, issn = {1877-0428}, doi = {10.1016/j.sbspro.2012.09.827}, pages = {1125 -- 1134}, language = {en} } @misc{DresslerStrehler, author = {Dressler, Daniel and Strehler, Martin}, title = {Polynomial-Time Algorithms for Special Cases of the Maximum Confluent Flow Problem}, series = {Discrete Applied Mathematics}, volume = {163}, journal = {Discrete Applied Mathematics}, number = {2}, issn = {0166-218X}, pages = {142 -- 154}, language = {en} } @phdthesis{Strehler, author = {Strehler, Martin}, title = {Signalized Flows - optimizing traffic signals and guideposts and related network flow problems}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-23637}, pages = {182}, language = {en} } @misc{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Traffic signal optimization using cyclically expanded networks}, series = {Networks}, volume = {65}, journal = {Networks}, number = {3}, doi = {10.1002/net.21601}, pages = {244 -- 261}, language = {en} } @misc{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Traffic signal optimization: combining static and dynamic models}, series = {arXiv.org}, journal = {arXiv.org}, pages = {29}, abstract = {In this paper, we present a cyclically time-expanded network model for simultaneous optimization of traffic assignment and traffic signal parameters, in particular offsets, split times, and phase orders. Since travel times are of great importance for developing realistic solutions for traffic assignment and traffic signal coordination in urban road networks, we perform an extensive analysis of the model. We show that a linear time-expanded model can reproduce realistic travel times especially for use with traffic signals and we verify this by simulation. Furthermore, we show how exact mathematical programming techniques can be used for optimizing the control of traffic signals. We provide computational results for real world instances and demonstrate the capabilities of the cyclically time-expanded by simulation results obtained with state-of-the-art traffic simulation tools.}, language = {en} } @inproceedings{MertingSchwanStrehler, author = {Merting, S{\"o}ren and Schwan, Christian and Strehler, Martin}, title = {Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes}, series = {15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)}, booktitle = {15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)}, editor = {Italiano, Giuseppe F. and Schmidt, Marie}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-939897-99-6}, doi = {10.4230/OASIcs.ATMOS.2015.29}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-54559}, pages = {29 -- 41}, abstract = {We consider a constrained shortest path problem with the possibility to refill the resource at certain nodes. This problem is motivated by routing electric vehicles with a comparatively short cruising range due to the limited battery capacity. Thus, for longer distances the battery has to be recharged on the way. Furthermore, electric vehicles can recuperate energy during downhill drive. We extend the common constrained shortest path problem to arbitrary costs on edges and we allow regaining resources at the cost of higher travel time. We show that this yields not shortest paths but shortest walks that may contain an arbitrary number of cycles. We study the structure of optimal solutions and develop approximation algorithms for finding short walks under mild assumptions on charging functions. We also address a corresponding network flow problem that generalizes these walks.}, language = {en} } @misc{SchwanStrehler, author = {Schwan, Christian and Strehler, Martin}, title = {Energy-efficient Routing of Hybrid Vehicles}, series = {arXiv.org}, journal = {arXiv.org}, pages = {11}, abstract = {We consider a constrained shortest path problem with two resources. These two resources can be converted into each other in a particular manner. Our practical application is the energy optimal routing of hybrid vehicles. Due to the possibility of converting fuel into electric energy this setting adds new characteristics and new combinatorial possibilities to the common constrained shortest path problem (CSP). We formulate the resulting problem as a generalization of CSP. We show that optimal paths in this model may contain cycles and we state conditions to prevent them. The main contribution is a polynomial-time approximation scheme and a simpler approximation algorithm for computing energy-optimal paths in graphs.}, language = {en} } @inproceedings{SchefflerStrehler, author = {Scheffler, Robert and Strehler, Martin}, title = {Optimizing Traffic Signal Timings for Mega Events}, series = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), ATMOS'16, August 25, 2016, Aarhus, Denmark}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), ATMOS'16, August 25, 2016, Aarhus, Denmark}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, doi = {10.4230/OASIcs.ATMOS.2016.8}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-66724}, pages = {8,1 -- 8,16}, language = {en} } @inproceedings{SchadeStrehler, author = {Schade, Stanley and Strehler, Martin}, title = {The Maximum Flow Problem for Oriented Flows}, series = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, doi = {10.4230/OASIcs.ATMOS.2016.7}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-65318}, pages = {1 -- 13}, abstract = {In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.}, language = {en} } @misc{StrehlerMertingSchwan, author = {Strehler, Martin and Merting, S{\"o}ren and Schwan, Christian}, title = {Energy-efficient shortest routes for electric and hybrid vehicles}, series = {Transportation Research Part B: Methodological}, volume = {Vol. 103}, journal = {Transportation Research Part B: Methodological}, issn = {0191-2615}, doi = {10.1016/j.trb.2017.03.007}, pages = {111 -- 135}, language = {en} } @inproceedings{StrehlerScheffler, author = {Strehler, Martin and Scheffler, Robert}, title = {Optimizing Traffic Signal Settings for Public Transport Priority}, series = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), September 7-8, 2017, Vienna, Austria}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017), September 7-8, 2017, Vienna, Austria}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik GmbH}, address = {Wadern}, isbn = {978-3-95977-042-2}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-79109}, pages = {9-1 -- 9-15}, language = {en} } @inproceedings{SchwanStrehler, author = {Schwan, Christian and Strehler, Martin}, title = {Two FPTAS for the Constrained Shortest Path Problem Applied to Hybrid Vehicle Routing}, series = {Proceedings of the Sixth International Conference on High Performance Scientific Computing, March 16-20, 2015, Hanoi, Vietnam}, booktitle = {Proceedings of the Sixth International Conference on High Performance Scientific Computing, March 16-20, 2015, Hanoi, Vietnam}, editor = {Bock, Hans Georg and Phu, Hoang Xuan and Rannacher, Rolf and Schl{\"o}der, Johannes}, edition = {1. Auflage}, publisher = {Springer International Publishing}, isbn = {978-3-319-67167-3}, doi = {10.1007/978-3-319-67168-0}, pages = {223 -- 234}, language = {en} } @inproceedings{SchefflerStrehlerVargasKoch, author = {Scheffler, Robert and Strehler, Martin and Vargas Koch, Laura}, title = {Equilibria in Routing Games with Edge Priorities}, series = {14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings}, booktitle = {14th International Conference, WINE 2018, Oxford, UK, December 15-17, 2018, Proceedings}, editor = {Christodoulou, George and Harks, Tobias}, publisher = {Springer International Publishing}, address = {Cham}, isbn = {978-3-030-04612-5}, doi = {10.1007/978-3-030-04612-5_27}, pages = {408 -- 422}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Recognizing Graph Search Trees}, series = {arXiv.org}, journal = {arXiv.org}, pages = {23}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {On the End-Vertex Problem of Graph Searches}, series = {Discrete Mathematics \& Theoretical Computer Science}, volume = {21}, journal = {Discrete Mathematics \& Theoretical Computer Science}, number = {1}, issn = {1365-8050}, language = {en} } @misc{ThunigSchefflerStrehleretal., author = {Thunig, Theresa and Scheffler, Robert and Strehler, Martin and Nagel, Kai}, title = {Optimization and simulation of fixed-time traffic signal control in real-world applications}, series = {8th International Workshop on Agent-based Mobility, Traffic and Transportation Models, Methodologies and Applications ABMTRANS'19}, journal = {8th International Workshop on Agent-based Mobility, Traffic and Transportation Models, Methodologies and Applications ABMTRANS'19}, publisher = {Elsevier}, address = {Amsterdam}, issn = {1877-0509}, doi = {10.1016/j.procs.2019.04.113}, pages = {826 -- 833}, language = {en} } @misc{BeisegelKoehlerScheffleretal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin}, title = {Linear Time LexDFS on Chordal Graphs}, series = {28th Annual European Symposium on Algorithms (ESA) 2020, September 7-9, 2020, Pisa, Italy)}, volume = {173}, journal = {28th Annual European Symposium on Algorithms (ESA) 2020, September 7-9, 2020, Pisa, Italy)}, publisher = {Schloss Dagstuhl, Leibnitz Zentrum f{\"u}r Informatik}, doi = {10.4230/LIPIcs.ESA.2020.13}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-128790}, pages = {13:1 -- 13:13}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {Recognizing Graph Search Trees}, series = {The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) 2-7 June 2019, Belo Horizonte, Brazil}, journal = {The proceedings of Lagos 2019, the tenth Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS 2019) 2-7 June 2019, Belo Horizonte, Brazil}, editor = {Coutinho, Gabriel and Kohayakawa, Yoshiharu and dos Santos, Vinicius and Urrutia, Sebasti{\´a}n}, publisher = {Elsevier}, issn = {1571-0661}, doi = {10.1016/j.entcs.2019.08.010}, pages = {99 -- 110}, language = {en} } @misc{KoehlerStrehler, author = {K{\"o}hler, Ekkehard and Strehler, Martin}, title = {Traffic Signal Optimization: Combining Static and Dynamic Models}, series = {Transportation Science}, volume = {53}, journal = {Transportation Science}, number = {1}, issn = {1526-5447}, doi = {10.1287/trsc.2017.0760}, pages = {21 -- 41}, language = {en} } @misc{BeisegelDenkertKoehleretal., author = {Beisegel, Jesse and Denkert, Carolin and K{\"o}hler, Ekkehard and Krnc, Matjaž and Pivač, Nevena and Scheffler, Robert and Strehler, Martin}, title = {The Recognition Problem of Graph Search Trees}, series = {SIAM Journal on Discrete Mathematics}, volume = {35}, journal = {SIAM Journal on Discrete Mathematics}, number = {2}, issn = {1095-7146}, doi = {10.1137/20M1313301}, pages = {1418 -- 1446}, language = {en} } @misc{KoehlerRoggeScheffleretal., author = {K{\"o}hler, Ekkehard and Rogge, Markus and Scheffler, Robert and Strehler, Martin}, title = {Optimal Bicycle Routes with Few Signal Stops}, series = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, volume = {OASIcs - Open Access Series in Informatics; Band 115}, journal = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, issn = {978-3-95977-302-7}, doi = {10.4230/OASIcs.ATMOS.2023.1}, pages = {1:1 -- 1:14}, language = {en} } @misc{BeisegelKoehlerRatajczaketal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Ratajczak, Fabienne and Scheffler, Robert and Strehler, Martin}, title = {Graph search trees and the intermezzo problem}, series = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, journal = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, editor = {Kr{\´a}lovič, Rastislav and Kučera, Anton{\´i}n}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl}, isbn = {978-3-95977-335-5}, doi = {10.4230/LIPICS.MFCS.2024.22}, pages = {22:1 -- 22:18}, language = {en} } @misc{BeisegelKoehlerScheffleretal., author = {Beisegel, Jesse and K{\"o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin}, title = {Certifying fully dynamic algorithms for recognition and Hamiltonicity of Threshold and Chain Graphs}, series = {Algorithmica}, volume = {85}, journal = {Algorithmica}, number = {8}, issn = {0178-4617}, doi = {10.1007/s00453-023-01107-1}, pages = {2454 -- 2481}, language = {en} } @misc{SchefflerStrehlerVargasKoch, author = {Scheffler, Robert and Strehler, Martin and Vargas Koch, Laura}, title = {Routing Games with Edge Priorities}, series = {ACM Transactions on Economics and Computation}, volume = {10}, journal = {ACM Transactions on Economics and Computation}, number = {1}, issn = {2167-8375}, doi = {10.1145/3488268}, pages = {1:1 -- 1:27}, language = {en} }