Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks

DOI10.1002/NET.22123MaRDI QIDQ6179710zbMATH OpenOpenAlexFDO

Authors Filippo Brunelli, Pilu Crescenzi, Laurent Viennot

Publication date 18 December 2023

Published in Networks (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/net.22123

zbMATH Keywords

edge labelingedge scheduled networknetwork optimizationtemporal graphtemporal pathtemporal reachabilitytime assignment

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Deterministic scheduling theory in operations research (90B35)

Recommendations

• Optimizing reachability sets in temporal graphs by delaying
• Assigning times to minimise reachability in temporal graphs
• On computing optimal temporal branchings and spanning subgraphs
• Traveling salesman problems in temporal graphs
• Traveling salesman problems in temporal graphs

Cites work

• A guide to temporal networks
• A survey of gossiping and broadcasting in communication networks
• An introduction to temporal graphs: an algorithmic perspective
• Assigning times to minimise reachability in temporal graphs
• Connection Scan Algorithm
• Connectivity and inference problems for temporal networks
• Deleting edges to restrict the size of an epidemic in temporal networks
• Dynamic graph models
• Encyclopedia of algorithms. In 3 volumes
• Finding Temporal Paths Under Waiting Time Constraints.
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 961960 (Why is no real title available?)
• Label-connected graphs and the gossip problem
• Nominal and robust train timetabling problems
• On computing Pareto optimal paths in weighted time-dependent networks
• Temporal network optimization subject to connectivity constraints
• Temporal network optimization subject to connectivity constraints
• Temporal Reachability Minimization: Delaying vs. Deleting
• The Complexity of Transitively Orienting Temporal Graphs
• The theory of dynamic programming
• Time-stamped graphs and their associated influence digraphs

Cited in

(3)

• Temporally connected components
• Temporalizing digraphs via linear-size balanced bi-trees
• Realization of temporally connected graphs based on degree sequences

This page was built for publication: Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks

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