Sparsest cuts and concurrent flows in pr
β
Paul Bonsma
π
Article
π
2004
π
Elsevier Science
π
English
β 300 KB
A cut [S; S] is a sparsest cut of a graph G if its cut value |S S|=|[S; S]| is maximum (this is the reciprocal of the well-known edge-density of the cut). In the (undirected) uniform concurrent ow problem on G, between every vertex pair of G ow paths with a total ow of 1 have to be established. The