Optimizing reachability sets in temporal graphs by delaying

DOI10.1016/j.ic.2022.104890zbMath1504.68160arXiv2004.05875OpenAlexW3015837792MaRDI QIDQ2672269

Argyrios Deligkas, Igor Potapov

Publication date: 8 June 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2004.05875

zbMATH Keywords

optimizationNP-hardnessreachability setstemporal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Disentangling the computational complexity of network untangling

Uses Software

• EpiContactTrace

Cites Work

• Unnamed Item
• Traveling salesman problems in temporal graphs
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The modeling of global epidemics: stochastic dynamics and predictability
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Temporal network optimization subject to connectivity constraints
• Computing parameters of sequence-based dynamic graphs
• The complexity of finding small separators in temporal graphs
• On decidability and complexity of low-dimensional robot games
• Assigning times to minimise reachability in temporal graphs
• Temporal flows in temporal networks
• On temporal graph exploration
• Deleting edges to restrict the size of an epidemic in temporal networks
• Cluster Editing in Multi-Layer and Temporal Graphs.
• Developments in Language Theory
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Temporal Reachability Minimization: Delaying vs. Deleting

This page was built for publication: Optimizing reachability sets in temporal graphs by delaying