A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs

DOI10.1016/j.dam.2019.12.012zbMath1460.90050OpenAlexW2999068266WikidataQ126403863 ScholiaQ126403863MaRDI QIDQ2664011

Yoann Pigné, Mathilde Vernet, Maciej Drozdowski, Eric Sanlaville

Publication date: 20 April 2021

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

Full work available at URL: https://doi.org/10.1016/j.dam.2019.12.012

zbMATH Keywords

minimum cost flowdynamic graphsuccessive shortest path algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Related Items (3)

Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ Invited paper: Simple, strict, proper, happy: a study of reachability in temporal graphs ⋮ GraphStream

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traveling salesman problems in temporal graphs
• Approximating earliest arrival flows with flow-dependent transit times
• An exact algorithm for a multicommodity min-cost flow over time problem
• On solving quickest time problems in time-dependent, dynamic networks
• Fast paths in large-scale dynamic road networks
• Temporal flows in temporal networks
• An approximation algorithm for discrete minimum cost flows over time problem
• The Quickest Transshipment Problem
• An Introduction to Network Flows over Time
• Maximal Flow Through a Network
• Minimum cost time-varying network flow problems
• Minimum Convex Cost Dynamic Network Flows
• A Class of Continuous Network Flow Problems
• Maximal, Lexicographic, and Dynamic Network Flows
• A generalized dynamic flows problem
• Minimum-cost dynamic flows: The series-parallel case
• On the Quickest Flow Problem in Dynamic Networks – A Parametric Min-Cost Flow Approach
• Constructing Maximal Dynamic Flows from Static Flows
• An Algorithm for Universal Maximal Dynamic Flows in a Network
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Time-varying minimum cost flow problems

This page was built for publication: A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs