| Resum: |
In this paper we discuss a number of recent and earlier results in the field of combinatorial optimization that concerns problems on minimum cost multiflows (multicommodity flows) and edge-disjoint paths. More precisely, we deal with an undirected network N consisting of a supply graph G, a commodity graph H and nonnegative integer-valued functions of capacities and costs of edges of G, and consider the problems of minimizing the total cost among (i) all maximum multiflows, and (ii) all maximum integer multiflows. For problem (i), we discuss the denominators behavior in terms of H. The main result is that if H is complete (i. e. flows between any two terminals are allowed) then (i) has a half-integer optimal solution. Moreover, there are polynomial algorithms to find such a solution. For problem (ii), we give an explicit combinatorial minimax relation in case of H complete. This generalizes a minimax relation, due to Mader and, independently, Lomonosov, for the maximum number of edge-disjoint paths whose ends belong to a prescribed subset of nodes of a graph. Also there exists a polynomial algorithm when the capacities are all-unit. The minimax relation for (ii) with H complete allows to describe the dominant for the set of (T, d)-joins (extending the notion of T-join) and the dominant for the set of maximum multi-joins of a graph. Also other relevant results are reviewed and open questions are raised. . |
visitant ::
identificació
Accés restringit a la UAB
