The multicommodity-flow tag has no wiki summary.
3
votes
1answer
142 views
How can we derive this lower bound of a special cut in a graph?
I have another question about this paper. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in ...
5
votes
1answer
164 views
Finding the perfomance ratio in a multicommodity-flow
I am reading the following paper about multicommodity-flows. I have not a very strong background in graph theory and hence most of my question regarding the paper are fundamental. My questions are ...
5
votes
0answers
171 views
On the optimal solution of the CKR formulation for MULTIWAY CUT
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
8
votes
1answer
192 views
Request for references on multicommodity flow-cut results
This is a somewhat subjective question. I am interested in studying the literature on multicommodity flow-cut results, especially the 'positive' results which show that flow is a good approximation to ...
6
votes
1answer
159 views
multi-commodity flow acyclic digraphs
I am faced with the following question on max. integer multiflow:
INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function ...
5
votes
1answer
330 views
On the faces of the multicommodity flow polytope
Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows ...
