Temporal reachability minimization: delaying vs. deleting

DOI10.1016/J.JCSS.2024.103549MaRDI QIDQ6564622zbMATH OpenFDO

Authors Hendrik Molter, Malte Renken, Philipp Zschoche

Publication date 1 July 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2024.103549

zbMATH Keywords

network flowsNP-hard problemsparameterized algorithmstemporal graphsdisease spreadingtemporal paths

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• scientific article; zbMATH DE number 7663122 (Why is no real title available?)
• A note on two problems in connexion with graphs
• Assigning times to minimise reachability in temporal graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Connectivity and inference problems for temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Editing graphs to satisfy degree constraints: a parameterized approach
• Faster exploration of degree-bounded temporal graphs
• Feedback edge sets in temporal graphs
• Finding temporal paths under waiting time constraints
• Fundamentals of parameterized complexity
• How fast can we reach a target vertex in stochastic temporal graphs?
• Maximal Flow Through a Network
• Non-strict Temporal Exploration
• On exploring always-connected temporal graphs of small pathwidth
• On finding separators in temporal split and permutation graphs
• On the size and the approximability of minimum temporally connected subgraphs
• Optimizing reachability sets in temporal graphs by delaying
• Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
• Relationships between nondeterministic and deterministic tape complexities
• Temporal Reachability Minimization: Delaying vs. Deleting
• Temporal cliques admit sparse spanners
• Temporal network optimization subject to connectivity constraints
• The complexity of computing optimum labelings for temporal connectivity
• The complexity of finding small separators in temporal graphs
• The complexity of finding temporal separators under waiting time constraints
• The temporal explorer who returns to the base
• Two moves per time step make a difference
• Undirected connectivity in log-space

Cited in

(3)

• Temporal graph realization with bounded stretch
• Temporal reachability dominating sets: contagion in temporal graphs
• Counting temporal paths

This page was built for publication: Temporal reachability minimization: delaying vs. deleting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6564622)