5
$\begingroup$

Usually in (integral) multi-commodity flow problems the graph is assumed to be directed. Instead, I am working with an undirected graph. Is it possible to transform it in a digraph?

Does such a transformation work in both the continuous and integral case?

$\endgroup$
7
$\begingroup$

Replace each undirected edge with two directed arcs in opposite directions. The original capacity constraint on each edge now applies to the sum of the arcs in both directions. If the costs are positive, every optimal solution will have flow in at most one of the two directions.

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! So, if I got it right: consider an undirected edge with capacity 1. The corresponding digraph will have 2 edges, both with capacity 1. Whilst the corresponding constraint is still upper-bounded by 1, but now it considers the sum of the flows. Would be great if you could share some reference on the topic. $\endgroup$ Oct 8 at 14:19
  • 1
    $\begingroup$ Network Flows (1993) discusses this transformation on page 39. $\endgroup$
    – RobPratt
    Oct 8 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.