Finding temporal paths under waiting time constraints
type: Item
instance of: scholarly article
title: Finding temporal paths under waiting time constraints
author: Arnaud Casteigts
author: Anne-Sophie Himmel
author: Hendrik Molter
author: Philipp Zschoche
published in: Algorithmica
publication date: 2021-09-02T00:00:00Z
full work available at URL: https://arxiv.org/abs/1909.06437
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7390201
zbMATH Keywords: temporal graphs
zbMATH Keywords: disease spreading
zbMATH Keywords: waiting-time policies
zbMATH Keywords: restless temporal paths
zbMATH Keywords: timed feedback vertex set
zbMATH Keywords: NP-hard problems
zbMATH Keywords: parameterized algorithms
MaRDI profile type: Publication
OpenAlex ID: W3166547661
cites work: Parameterized complexity of conflict-free matchings and paths
cites work: Proofs from THE BOOK
cites work: The complexity of optimal design of temporally connected graphs
cites work: Temporal flows in temporal networks
cites work: How fast can we reach a target vertex in stochastic temporal graphs?
cites work: On the Size and the Approximability of Minimum Temporally Connected Subgraphs
cites work: Q3452868
cites work: An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
cites work: Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
cites work: Q5689807
cites work: Interval scheduling and colorful independent sets
cites work: Kernelization Lower Bounds by Cross-Composition
cites work: COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
cites work: On the expressivity of time-varying graphs
cites work: Temporal cliques admit sparse spanners
cites work: Q3651735
cites work: Subset Feedback Vertex Set Is Fixed-Parameter Tractable
cites work: Parameterized Algorithms
cites work: Graph Theory
cites work: Deleting edges to restrict the size of an epidemic in temporal networks
cites work: An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Temporal graph classes: a view through temporal separators
cites work: Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
cites work: Representative Families of Product Families
cites work: The directed subgraph homeomorphism problem
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Temporal Network Theory
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Half-integrality, LP-branching, and FPT algorithms
cites work: Reducibility among Combinatorial Problems
cites work: Connectivity and inference problems for temporal networks
cites work: Deterministic Truncation of Linear Matroids
cites work: Q4993296
cites work: A parameterized view on matroid optimization problems
cites work: Temporal network optimization subject to connectivity constraints
cites work: An Introduction to Temporal Graphs: An Algorithmic Perspective*
cites work: Sparsity. Graphs, structures, and algorithms
cites work: Networks
cites work: Q3135082
cites work: Deterministic methods to find primes
cites work: A simplified NP-complete satisfiability problem
cites work: Finding paths of length \(k\) in \(O^{*}(2^k)\) time
cites work: The complexity of finding small separators in temporal graphs
DOI: 10.1007/S00453-021-00831-W
description: scientific article; zbMATH DE number 7390201