Hi there.. I have a network (a graph undirected and unweighted) and I need to find kpaths between any pair of nodes. How can I do this?
1 Answer
my understanding that this basically can be done by linear programming, as a variation of the classical maxflow mincut approach. See this paper in J. Graph Theory 67(2011) 3437.
Needless to say, in the nondirected case one can replace each edge by a pair of arcs going in opposite directions.

$\begingroup$ but in my case, the graph is undirected and unweighted. In your paper, the theorem uses a directed and weighted graph. $\endgroup$– ReneDec 14, 2012 at 13:54

1$\begingroup$ so your case is a subcase of the situation considered in the paper! $\endgroup$ Dec 14, 2012 at 13:59