Finding temporal paths under waiting time constraints
From MaRDI portal
Publication:1979453
DOI10.1007/s00453-021-00831-wOpenAlexW3166547661MaRDI QIDQ1979453
Hendrik Molter, Arnaud Casteigts, Philipp Zschoche, Anne-Sophie Himmel
Publication date: 2 September 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1909.06437
NP-hard problemsparameterized algorithmstemporal graphsdisease spreadingrestless temporal pathstimed feedback vertex setwaiting-time policies
Related Items (22)
As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Mengerian temporal graphs revisited ⋮ Maximum 0-1 timed matching on temporal graphs ⋮ Towards classifying the polynomial-time solvability of temporal betweenness centrality ⋮ Non-strict Temporal Exploration ⋮ Mengerian graphs: characterization and recognition ⋮ Towards Classifying the Polynomial-Time Solvability of Temporal Betweenness Centrality ⋮ Multistage \(s-t\) path: confronting similarity with dissimilarity ⋮ Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Sharp Thresholds in Random Simple Temporal Graphs ⋮ Disentangling the computational complexity of network untangling ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Computing maximum matchings in temporal graphs ⋮ Parameterised temporal exploration problems ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ A faster parameterized algorithm for temporal matching ⋮ The complexity of finding temporal separators under waiting time constraints ⋮ Finding colorful paths in temporal graphs ⋮ Foremost non-stop journey arrival in linear time ⋮ Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- On the parameterized complexity of multiple-interval graph problems
- A parameterized view on matroid optimization problems
- The directed subgraph homeomorphism problem
- Which problems have strongly exponential complexity?
- Temporal network optimization subject to connectivity constraints
- The complexity of finding small separators in temporal graphs
- Temporal cliques admit sparse spanners
- 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
- Half-integrality, LP-branching, and FPT Algorithms
- Graph Theory
- Subset Feedback Vertex Set Is Fixed-Parameter Tractable
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Deterministic Truncation of Linear Matroids
- An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
- Networks
- On the Size and the Approximability of Minimum Temporally Connected Subgraphs
- Representative Families of Product Families
- Kernelization Lower Bounds by Cross-Composition
- Reducibility among Combinatorial Problems
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Temporal Network Theory
- Deterministic methods to find primes
- 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
- Proofs from THE BOOK
- Temporal graph classes: a view through temporal separators
- On the complexity of \(k\)-SAT
This page was built for publication: Finding temporal paths under waiting time constraints
