The dynamic Steiner tree problem: definitions, complexity, algorithms

DOI10.1016/J.DAM.2026.06.001MaRDI QIDQ7304707zbMATH OpenFDO

Authors Stefan Balev, Yoann Pigné, Eric Sanlaville, Mathilde Vernet

Publication date 28 July 2026

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2026.06.001

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Cites work

• A study of connectivity on dynamic graphs: computing persistent connected components
• A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs
• An introduction to network flows over time
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Constructing maximal dynamic flows from static flows
• Efficiently testing T-interval connectivity in dynamic graphs
• Flooding time in edge-Markovian dynamic graphs
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Reducibility among combinatorial problems
• Statistical mechanics of complex networks
• Steiner trees, connected domination and strongly chordal graphs
• Temporal cliques admit sparse spanners
• Temporally connected components
• The complexity of computing optimum labelings for temporal connectivity
• Traveling salesman problems in temporal graphs

This page was built for publication: The dynamic Steiner tree problem: definitions, complexity, algorithms

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