Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.

enter image description here

We now show how to transform a minimum cut problem on an s-t planar network (s means source and t means sink) into a shortest path problem. In the given s-t planar network, we first draw a new arc joining the nodes s and t so that the arc stays within the unbounded face of the network [see Figure 8.8(b)]; this construction creates a new face of the network, which we call the additional face, but maintains the network's planarity. We then construct the dual of this network; we designate the node corresponding to the additional face as the dual source s * and the node corresponding to the unbounded face as the dual sink t*. We set the cost of an arc in the dual network equal to the capacity of the corresponding arc in the primal network. The dual network contains the arc (s*, t*) which we delete from the network. Figure 8.8(b) shows this construction: the dashed lines are the arcs in the dual network.

  1. How shall I understand the one before the last sentence "The dual network contains the arc (s*, t*) which we delete from the network"? Why I don't see an arc between s* and t* in the dual network?
  2. Does the dash arc (s, t) constructed at the beginning belong to the dual network? I guess not, because s and t are not vertices in the dual graph, isn't it?

Thanks and regards!

share|improve this question

1 Answer 1

up vote 2 down vote accepted
  1. The network in (b) shows the situation after deletion of the $(s^*, t^*)$ arc. The $(s^*, t^*)$ arc needs to be removed in order to have a one-to-one correspondence between $s$-$t$ cuts in the primal and paths from $s^*$ to $t^*$ in the dual.

  2. No, it doesn't belong to the dual network. Dual arcs must be between faces in the primal network. I'm not sure why they left it in figure (b), as it is a bit confusing to have it there.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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