Min-cost multiflows in node-capacitated undirected networks

Maxim A. Babenko () and Alexander Karzanov
Additional contact information
Maxim A. Babenko: Moscow State University

Journal of Combinatorial Optimization, 2012, vol. 24, issue 3, No 5, 202-228

Abstract: Abstract We consider an undirected graph G=(VG,EG) with a set T⊆VG of terminals, and with nonnegative integer capacities c(v) and costs a(v) of nodes v∈VG. A path in G is a T-path if its ends are distinct terminals. By a multiflow we mean a function F assigning to each T-path P a nonnegative rational weight F(P), and a multiflow is called feasible if the sum of weights of T-paths through each node v does not exceed c(v). The value of F is the sum of weights F(P), and the cost of F is the sum of F(P) times the cost of P w.r.t. a, over all T-paths P. Generalizing known results on edge-capacitated multiflows, we show that the problem of finding a minimum cost multiflow among the feasible multiflows of maximum possible value admits half-integer optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

Keywords: Minimum cost multiflow; Bidirected graph; Skew-symmetric graph (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9377-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:3:d:10.1007_s10878-011-9377-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9377-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().