Multiflows and disjoint paths of minimum total cost
Karzanov, Alexander V.

Data: 1997
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. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Multicommodity flow ; Disjoint paths ; Dominant
Publicat a: Mathematical Programming, vol. 78 n. 2 (1997) p. 219-242, ISSN 0025-5610

24 p, 1.3 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir