SRC Technical Note 1997-022

Short-Length Menger Theorems

Monika Rauch Henzinger, Jon Kleinberg, Satish Rao

We give short and simple proofs of the following two theorems by Galil and Yu. Let s and t be two vertices in an n-node graph G. (1) There exist k edge-disjoint s-t paths of total length O(n k^{1/2). (2) If we additionally assume that the minimum degree of G is at least k, then there exist k edge-disjoint s-t paths, each of length O(n/k).

Back to the SRC Technical Notes main page.

• PostScript compressed with UNIX compress -- 80 Kbytes
  
• PostScript compressed with GNU compress (gzip) -- 72 Kbytes
  
• PostScript compressed with ZIP -- 72 Kbytes
  
• PostScript -- 136 Kbytes
  
• Portable Document Format (PDF) -- 23 Kbytes