Tell me more ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

I've been attempting to read Goldberg & Rao's paper Beyond the flow decomposition barrier, and found that I could not understand the blocking flow component of the paper. I then found Karger's lecture notes from MIT's Adv. Algorithms course. I found this much more approachable, but could not understand one portion of the explanation of the Blocking flow procedure.

Karger proves a Lemma which states that "augmenting along a blocking flow increases the distance between $s$ and $t$, which is understandable, but then finds a corollary due to (1) the lemma as well as the fact that (2) the length of each $s-t$ path is at most $n$, where $n=|V|$. Where does Karger's second assertion come from? The only example I can come up with is the case where

$$ s --1-- O --1--O --1-- t $$ But this still has a length $l=n-1=4$ of the $s-t$ path. In which case will $l=n=5$?

share|improve this question

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.