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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Dec 14, 2012 at 13:54
  • 1
    $\begingroup$ so your case is a subcase of the situation considered in the paper! $\endgroup$
    – Dima Pasechnik
    Commented Dec 14, 2012 at 13:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .