[igraph] mincut/maxflow efficiency question

[Benjamin Fields]

Hi List - 

I' m interesting in calculating a number of mincut/maxflow values from and unweighted undirected graph in order to determine independent path counts between pairs of nodes.  I have a graph of ~15k vertices and ~92k edges and there are around 13k vertices pairs I need to determine these values for.  As such I'm wondering about the most efficient way to go about this.  My network flow analysis background is light at best so I'm starting from the ground up here.  My specific question as a first approach is this: at the implementation level is there any difference between maxflow_value and mincut_value in terms of how fast the run on unweighted undirected graphs?  Also, if anyone has any other efficiency suggestions they would be much appreciated.  Thanks in advance for any help.

cheers

Ben

Ben Fields
PhD Candidate
Dept. of Computing
Goldsmiths, University of London
e: address@hidden
p: +44 (0) 20 7078 5170

---------------------------------------------

"Which is more musical: a truck passing by a factory or a truck passing by a music school?" --John Cage