Search Results

Documents authored by Strehler, Martin

Document
DOI: 10.4230/LIPIcs.MFCS.2024.22
Graph Search Trees and the Intermezzo Problem

Authors: Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, and Martin Strehler

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
The last in-tree recognition problem asks whether a given spanning tree can be derived by connecting each vertex with its rightmost left neighbor of some search ordering. In this study, we demonstrate that the last-in-tree recognition problem for Generic Search is NP-complete. We utilize this finding to strengthen a complexity result from order theory. Given a partial order π and a set of triples, the NP-complete intermezzo problem asks for a linear extension of π where each first element of a triple is not between the other two. We show that this problem remains NP-complete even when the Hasse diagram of the partial order forms a tree of bounded height. In contrast, we give an XP-algorithm for the problem when parameterized by the width of the partial order. Furthermore, we show that - under the assumption of the Exponential Time Hypothesis - the running time of this algorithm is asymptotically optimal.
Cite as

Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, and Martin Strehler. Graph Search Trees and the Intermezzo Problem. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.MFCS.2024.22,
  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}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.22},
  URN =		{urn:nbn:de:0030-drops-205781},
  doi =		{10.4230/LIPIcs.MFCS.2024.22},
  annote =	{Keywords: graph search trees, intermezzo problem, algorithm, parameterized complexity}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.1
Optimal Bicycle Routes with Few Signal Stops

Authors: Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
With the increasing popularity of cycling as a mode of transportation, there is a growing need for efficient routing algorithms that consider the specific requirements of cyclists. This paper studies the optimization of bicycle routes while minimizing the number of stops at traffic signals. In particular, we consider three different types of stopping strategies and three types of routes, namely paths, trails, and walks. We present hardness results as well as a pseudo-polynomial algorithm for the problem of computing an optimal route with respect to a pre-defined stop bound.
Cite as

Ekkehard Köhler, Markus Rogge, Robert Scheffler, and Martin Strehler. Optimal Bicycle Routes with Few Signal Stops. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 1:1-1:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kohler_et_al:OASIcs.ATMOS.2023.1,
  author =	{K\"{o}hler, Ekkehard and Rogge, Markus and Scheffler, Robert and Strehler, Martin},
  title =	{{Optimal Bicycle Routes with Few Signal Stops}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{1:1--1:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.1},
  URN =		{urn:nbn:de:0030-drops-187628},
  doi =		{10.4230/OASIcs.ATMOS.2023.1},
  annote =	{Keywords: Constrained shortest path, traffic signals, bicycle routes}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.13
Linear Time LexDFS on Chordal Graphs

Authors: Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used in various applications, in contrast to other graph searches, no general linear time implementation is known to date. In 2014, Köhler and Mouatadid achieved linear running time to compute some special LexDFS orderings for cocomparability graphs. In this paper, we present a linear time implementation of LexDFS for chordal graphs. Our algorithm even implements the extended version LexDFS^+ and is, therefore, able to find any LexDFS ordering for this graph class. To the best of our knowledge this is the first unrestricted linear time implementation of LexDFS on a non-trivial graph class. In the algorithm we use a search tree computed by Lexicographic Breadth First Search (LexBFS).
Cite as

Jesse Beisegel, Ekkehard Köhler, Robert Scheffler, and Martin Strehler. Linear Time LexDFS on Chordal Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.ESA.2020.13,
  author =	{Beisegel, Jesse and K\"{o}hler, Ekkehard and Scheffler, Robert and Strehler, Martin},
  title =	{{Linear Time LexDFS on Chordal Graphs}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.13},
  URN =		{urn:nbn:de:0030-drops-128790},
  doi =		{10.4230/LIPIcs.ESA.2020.13},
  annote =	{Keywords: LexDFS, chordal graphs, linear time implementation, search trees, LexBFS}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2017.9
Optimizing Traffic Signal Settings for Public Transport Priority

Authors: Robert Scheffler and Martin Strehler

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Abstract
In order to promote public transport many municipalities use traffic signal control with a priority for buses or trams. In this paper, we address the problem of finding optimal passive transit signal priority settings. Building on a cyclically time-expanded network model for the combined traffic assignment traffic signal coordination problem, we introduce a suitable queuing model and several modifications to model public transport vehicles appropriately. We evaluate the applicability of this approach by computing and analyzing optimal solutions for several instances of a real-world scenario.
Cite as

Robert Scheffler and Martin Strehler. Optimizing Traffic Signal Settings for Public Transport Priority. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{scheffler_et_al:OASIcs.ATMOS.2017.9,
  author =	{Scheffler, Robert and Strehler, Martin},
  title =	{{Optimizing Traffic Signal Settings for Public Transport Priority}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{9:1--9:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.9},
  URN =		{urn:nbn:de:0030-drops-79005},
  doi =		{10.4230/OASIcs.ATMOS.2017.9},
  annote =	{Keywords: transit signal priority, traffic flow, traffic signal optimization, cyclically time-expanded network, public transport}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.7
The Maximum Flow Problem for Oriented Flows

Authors: Stanley Schade and Martin Strehler

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

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.
Cite as

Stanley Schade and Martin Strehler. The Maximum Flow Problem for Oriented Flows. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{schade_et_al:OASIcs.ATMOS.2016.7,
  author =	{Schade, Stanley and Strehler, Martin},
  title =	{{The Maximum Flow Problem for Oriented Flows}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{7:1--7:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.7},
  URN =		{urn:nbn:de:0030-drops-65318},
  doi =		{10.4230/OASIcs.ATMOS.2016.7},
  annote =	{Keywords: network flow with orientation, graph expansion, approximation, container logistics, train routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2016.8
Optimizing Traffic Signal Timings for Mega Events

Authors: Robert Scheffler and Martin Strehler

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract
Most approaches for optimizing traffic signal timings deal with the daily traffic. However, there are a few occasional events like football matches or concerts of musicians that lead to exceptional traffic situations. Still, such events occur more or less regularly and place and time are known in advance. Hence, it is possible to anticipate such events with special signal timings. In this paper, we present an extension of a cyclically time-expanded network flow model and a corresponding mixed-integer linear programming formulation for simultaneously optimizing traffic signal timings and traffic assignment for such events. Besides the mathematical analysis of this approach, we demonstrate its capabilities by computing signal timings for a real world scenario.
Cite as

Robert Scheffler and Martin Strehler. Optimizing Traffic Signal Timings for Mega Events. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{scheffler_et_al:OASIcs.ATMOS.2016.8,
  author =	{Scheffler, Robert and Strehler, Martin},
  title =	{{Optimizing Traffic Signal Timings for Mega Events}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{8:1--8:16},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.8},
  URN =		{urn:nbn:de:0030-drops-65323},
  doi =		{10.4230/OASIcs.ATMOS.2016.8},
  annote =	{Keywords: traffic flow, traffic signal timings, cyclically time-expanded network, mega event, exceptional traffic}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2015.29
Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes

Authors: Sören Merting, Christian Schwan, and Martin Strehler

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

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.
Cite as

Sören Merting, Christian Schwan, and Martin Strehler. Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 29-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{merting_et_al:OASIcs.ATMOS.2015.29,
  author =	{Merting, S\"{o}ren and Schwan, Christian and Strehler, Martin},
  title =	{{Routing of Electric Vehicles: Constrained Shortest Path Problems with Resource Recovering Nodes}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{29--41},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.29},
  URN =		{urn:nbn:de:0030-drops-54559},
  doi =		{10.4230/OASIcs.ATMOS.2015.29},
  annote =	{Keywords: routing of electric vehicles, constrained shortest paths, FPTAS, con- strained network flow}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.114
Traffic Signal Optimization Using Cyclically Expanded Networks

Authors: Ekkehard Köhler and Martin Strehler

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
Traditionally, the coordination of multiple traffic signals and the traffic assignment problem in an urban street network are considered as two separate optimization problems. However, it is easy to see that the traffic assignment has an influence on the optimal signal coordination and, vice versa, a change in the signal coordination changes the optimal traffic assignment. In this paper we present a cyclically time-expanded network and a corresponding mixed integer linear programming formulation for simultaneously optimizing both the coordination of traffic signals and the traffic assignment in an urban street network. Although the new cyclically time-expanded network provides a model of both traffic and signals close to reality, it still has the advantage of a linear objective function. Using this model we compute optimized signal coordinations and traffic assignment on real-world street networks. To evaluate the practical relevance of the computed solutions we conduct extensive simulation experiments using two established traffic simulation tools that reveal the advantages of our model.
Cite as

Ekkehard Köhler and Martin Strehler. Traffic Signal Optimization Using Cyclically Expanded Networks. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 114-129, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kohler_et_al:OASIcs.ATMOS.2010.114,
  author =	{K\"{o}hler, Ekkehard and Strehler, Martin},
  title =	{{Traffic Signal Optimization Using Cyclically Expanded Networks}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{114--129},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.114},
  URN =		{urn:nbn:de:0030-drops-27542},
  doi =		{10.4230/OASIcs.ATMOS.2010.114},
  annote =	{Keywords: dynamic flow, traffic optimization, traffic signals}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact