MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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.

share|cite|improve this answer
but in my case, the graph is undirected and unweighted. In your paper, the theorem uses a directed and weighted graph. – Rene Dec 14 '12 at 13:54
so your case is a subcase of the situation considered in the paper! – Dima Pasechnik Dec 14 '12 at 13:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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