# Minimum-cost dynamic flows: The series-parallel case

Klinz, Bettina
and
Woeginger, Gerhard J.
(2004)
*Minimum-cost dynamic flows: The series-parallel case.*
Networks, 43
(3).
pp. 153-162.
ISSN 0028-3045

PDF
Restricted to UT campus only : Request a copy 143kB |

Abstract: | A dynamic network consists of a directed graph with capacities, costs, and integral transit times on the arcs. In the minimum-cost dynamic flow problem (MCDFP), the goal is to compute, for a given dynamic network with source s, sink t, and two integers v and T, a feasible dynamic flow from s to t of value v, obeying the time bound T, and having minimum total cost. MCDFP contains as subproblems the minimum-cost maximum dynamic flow problem, where v is fixed to the maximum amount of flow that can be sent from s to t within time T and the minimum-cost quickest flow problem, where is T is fixed to the minimum time needed for sending v units of flow from s to t. We first prove that both subproblems are NP-hard even on two-terminal series-parallel graphs with unit capacities. As main result, we formulate a greedy algorithm for MCDFP and provide a full characterization via forbidden subgraphs of the class of graphs, for which this greedy algorithm always yields an optimum solution (for arbitrary choices of problem parameters). G is a subclass of the class of two-terminal series-parallel graphs. We show that the greedy algorithm solves MCDFP restricted to graphs in G in polynomial time. |

Item Type: | Article |

Copyright: | © 2004 Wiley InterScience |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/72005 |

Official URL: | http://dx.doi.org/10.1002/net.10112 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 219742