On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks

Details On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks

2009-12-31

arxiv.org/abs/1001.0125v2

Mathematics

Combinatorics

26 pages; improved presentation; replaced skew-symmetric graphs with bidirected ones in the main content; accepted to Journal

Scientific paper

We consider an undirected graph $G = (VG, EG)$ with a set $T \subseteq VG$ of terminals, and with nonnegative integer capacities $c(v)$ and costs $a(v)$ of nodes $v\in VG$. A path in $G$ is a \emph{$T$-path} if its ends are distinct terminals. By a \emph{multiflow} we mean a function $F$ assigning to each $T$-path $P$ a nonnegative rational \emph{weight} $F(P)$, and a multiflow is called \emph{feasible} if the sum of weights of $T$-paths through each node $v$ does not exceed $c(v)$. The \emph{value} of $F$ is the sum of weights $F(P)$, and the \emph{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 \emph{half-integer} optimal primal and dual solutions. Moreover, we devise a strongly polynomial algorithm for finding such optimal solutions.

Affiliated with

Also associated with

No associations

Rating

On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Min-Cost Multiflow Problem in Node-Capacitated Undirected Networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-104521