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

optimal branchingoptimal temporal walktemporal branchingtemporal graphtemporal networktemporal spanning subgraph

Mathematics Subject Classification ID

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

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

• An introduction to temporal graphs: an algorithmic perspective
• Anomaly detection in dynamic networks: a survey
• Components in time-varying graphs
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• 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
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• Introduction to algorithms
• On computing optimal temporal branchings
• On Computing the Diameter of (Weighted) Link Streams
• 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

(5)

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

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)