On computing optimal temporal branchings and spanning subgraphs

DOI10.1016/J.JCSS.2024.103596MaRDI QIDQ6655668zbMATH OpenFDO

Authors Daniela Bubboloni, Costanza Catalano, Andrea Marino, Ana Silva

Publication date 27 December 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.103596

zbMATH Keywords

temporal networktemporal graphoptimal branchingoptimal temporal walktemporal branchingtemporal spanning subgraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Edge-disjoint branchings in temporal digraphs
• Edge-Disjoint Branchings in Temporal Graphs
• Traveling salesman problems in temporal graphs
• On the enumeration of bicriteria temporal paths
• Traveling salesman problems in temporal graphs

Cites work

• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• An introduction to temporal graphs: an algorithmic perspective
• Anomaly detection in dynamic networks: a survey
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Components in time-varying graphs
• Connection Scan Algorithm
• Connectivity and inference problems for temporal networks
• Containment control of directed networks with time-varying nonlinear multi-agents using minimum number of leaders
• Contrasting the spread of misinformation in online social networks
• Discrete mathematics
• Edge-Disjoint Branchings in Temporal Graphs
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Eulerian walks in temporal graphs
• Finding temporal paths under waiting time constraints
• Introduction to algorithms
• On Computing the Diameter of (Weighted) Link Streams
• On computing optimal temporal branchings
• On packing arborescences in temporal networks
• Optimizing reachability sets in temporal graphs by delaying
• Simple, strict, proper, happy: a study of reachability in temporal graphs
• Temporal network optimization subject to connectivity constraints
• The complexity of finding small separators in temporal graphs
• The complexity of optimal design of temporally connected graphs
• The complexity of theorem-proving procedures

Cited in

(4)

• Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks
• Shortest Journeys in Directed Temporal Graphs
• On the complexity of temporal arborescence reconfiguration
• Edge-Disjoint Branchings in Temporal Graphs

This page was built for publication: On computing optimal temporal branchings and spanning subgraphs

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