Finding Temporal Paths Under Waiting Time Constraints.

DOI10.4230/lipics.isaac.2020.30OpenAlexW3111728162MaRDI QIDQ6065432

Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, Philipp Zschoche

Publication date: 14 November 2023

Full work available at URL: https://doi.org/10.4230/LIPIcs.ISAAC.2020.30

zbMATH Keywords

NP-hard problemsparameterized algorithmstemporal graphsdisease spreadingrestless temporal pathstimed feedback vertex setwaiting-time policies

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (2)

Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks ⋮ Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Sparsity. Graphs, structures, and algorithms
• A simplified NP-complete satisfiability problem
• Interval scheduling and colorful independent sets
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• A parameterized view on matroid optimization problems
• The directed subgraph homeomorphism problem
• Which problems have strongly exponential complexity?
• Enumerating maximal cliques in link streams with durations
• Temporal network optimization subject to connectivity constraints
• The complexity of finding small separators in temporal graphs
• Parameterized complexity of conflict-free matchings and paths
• How fast can we reach a target vertex in stochastic temporal graphs?
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• On the expressivity of time-varying graphs
• The complexity of optimal design of temporally connected graphs
• Temporal flows in temporal networks
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Deleting edges to restrict the size of an epidemic in temporal networks
• Graph Theory
• Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
• Deterministic Truncation of Linear Matroids
• Networks
• On the Size and the Approximability of Minimum Temporally Connected Subgraphs
• Representative Families of Product Families
• Temporal Cliques Admit Sparse Spanners
• Temporal Network Theory
• Parameterized Algorithms
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Temporal graph classes: a view through temporal separators
• Feedback edge sets in temporal graphs
• On the complexity of \(k\)-SAT

This page was built for publication: Finding Temporal Paths Under Waiting Time Constraints.