1
$\begingroup$

Hi there.. I have a network (a graph undirected and unweighted) and I need to find k-paths between any pair of nodes. How can I do this?

$\endgroup$

1 Answer 1

1
$\begingroup$

my understanding that this basically can be done by linear programming, as a variation of the classical max-flow min-cut approach. See this paper in J. Graph Theory 67(2011) 34-37.

Needless to say, in the non-directed case one can replace each edge by a pair of arcs going in opposite directions.

$\endgroup$
2
  • $\begingroup$ but in my case, the graph is undirected and unweighted. In your paper, the theorem uses a directed and weighted graph. $\endgroup$
    – Rene
    Dec 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.