3 Search Results for "Füchsle, Eugen"

Document
DOI: 10.4230/LIPIcs.ESA.2024.11
How to Reduce Temporal Cliques to Find Sparse Spanners

Authors: Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Many real-world networks, such as transportation or trade networks, are dynamic in the sense that the edge-set may change over time, but these changes are known in advance. This behavior is captured by the temporal graphs model, which has recently become a trending topic in theoretical computer science. A core open problem in the field is to prove the existence of linear-size temporal spanners in temporal cliques, i.e., sparse subgraphs of complete temporal graphs that ensure all-pairs reachability via temporal paths. So far, the best known result is the existence of temporal spanners with 𝒪(nlog n) many edges. We present significant progress towards proving whether linear-size temporal spanners exist in all temporal cliques. We adapt techniques used in previous works and heavily expand and generalize them. This allows us to show that the existence of a linear spanner in cliques and bi-cliques is equivalent and using this, we provide a simpler and more intuitive proof of the 𝒪(nlog n) bound by giving an efficient algorithm for finding linearithmic spanners. Moreover, we use our novel and efficiently computable approach to show that a large class of temporal cliques, called edge-pivotable graphs, admit linear-size temporal spanners. To contrast this, we investigate other classes of temporal cliques that do not belong to the class of edge-pivotable graphs. We introduce two such graph classes and we develop novel algorithmic techniques for establishing the existence of linear temporal spanners in these graph classes as well.
Cite as

Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells. How to Reduce Temporal Cliques to Find Sparse Spanners. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angrick_et_al:LIPIcs.ESA.2024.11,
  author =	{Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin},
  title =	{{How to Reduce Temporal Cliques to Find Sparse Spanners}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{11:1--11:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.11},
  URN =		{urn:nbn:de:0030-drops-210822},
  doi =		{10.4230/LIPIcs.ESA.2024.11},
  annote =	{Keywords: Temporal Graphs, temporal Clique, temporal Spanner, Reachability, Graph Connectivity, Graph Sparsification}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.17
Temporal Connectivity: Coping with Foreseen and Unforeseen Delays

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
Consider planning a trip in a train network. In contrast to, say, a road network, the edges are temporal, i.e., they are only available at certain times. Another important difficulty is that trains, unfortunately, sometimes get delayed. This is especially bad if it causes one to miss subsequent trains. The best way to prepare against this is to have a connection that is robust to some number of (small) delays. An important factor in determining the robustness of a connection is how far in advance delays are announced. We give polynomial-time algorithms for the two extreme cases: delays known before departure and delays occurring without prior warning (the latter leading to a two-player game scenario). Interestingly, in the latter case, we show that the problem becomes PSPACE-complete if the itinerary is demanded to be a path.
Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Temporal Connectivity: Coping with Foreseen and Unforeseen Delays. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuchsle_et_al:LIPIcs.SAND.2022.17,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Temporal Connectivity: Coping with Foreseen and Unforeseen Delays}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.17},
  URN =		{urn:nbn:de:0030-drops-159598},
  doi =		{10.4230/LIPIcs.SAND.2022.17},
  annote =	{Keywords: Paths and walks in temporal graphs, static expansions of temporal graphs, two-player games, flow computations, dynamic programming, PSPACE-completeness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.30
Delay-Robust Routes in Temporal Graphs

Authors: Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable - in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.
Cite as

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Delay-Robust Routes in Temporal Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fuchsle_et_al:LIPIcs.STACS.2022.30,
  author =	{F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte},
  title =	{{Delay-Robust Routes in Temporal Graphs}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.30},
  URN =		{urn:nbn:de:0030-drops-158403},
  doi =		{10.4230/LIPIcs.STACS.2022.30},
  annote =	{Keywords: algorithms and complexity, parameterized complexity, time-varying networks, temporal paths, journeys}
}
  • Refine by Author
  • 2 Füchsle, Eugen
  • 2 Molter, Hendrik
  • 2 Niedermeier, Rolf
  • 2 Renken, Malte
  • 1 Angrick, Sebastian
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Paths and connectivity problems
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Graph Connectivity
  • 1 Graph Sparsification
  • 1 PSPACE-completeness
  • 1 Paths and walks in temporal graphs
  • 1 Reachability
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 2022
  • 1 2024

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