0
votes
0answers
36 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0
votes
1answer
33 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
1
vote
1answer
56 views

Enquiry to network flow

Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear ...
0
votes
1answer
50 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
1answer
326 views

Multicommodity flow in polynomial size

The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size? Linear program of multicommodity flow $maximize ...
1
vote
1answer
71 views

Does the sparsest cut always have a solution?

How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset? It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't ...
2
votes
1answer
135 views

Sparsest cut is solvable on trees

The problem is to prove that Sparsest cut is solvable on trees in polynomial time. A short review, a sparsest cut is linear program $$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$ where ...
4
votes
1answer
190 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
1
vote
1answer
511 views

What is the restriction matrix used for in the stepping stone method?

Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1...m, demand nodes ...