There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. Is there any work about this?

1 Andrew V Goldberg and Robert E Tarjan. A new approach to the maximum-flow problem. Journal of the ACM (JACM), 35(4):921–940, 1988. google scholar

  • $\begingroup$ Can you perhaps describe the parallelization you have in mind or at least add a link to a description? $\endgroup$
    – Jan Hudec
    Oct 31 '14 at 13:08
  • $\begingroup$ @JanHudec I added a reference to the paper I read. But I'm open to any other parallelization approach. $\endgroup$
    – jederik
    Oct 31 '14 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.