Minimum cost dynamic flows: The series-parallel case

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