Talk:Max-flow min-cut theorem

From Wikipedia, the free encyclopedia

You have new messages (last change).

I propose pulling out the definition of the max flow problem as part of a separate page on the maximum flow problem. The new page might be structured like so:

  • Definition
  • Related problems, reductions from:
    • multiple source/sinks
    • maximum bipartite graph matching)
  • Methods for solving
    • Ford-Fulkerson
    • Push-relabel (aka preflow relabel)

The max flow min cut theorem is certainly central to proving the correctness of both methods.

Thoughts? Comments? Cries of dismay? --NikolasCo 06:38, 22 December 2005 (UTC)

Ooops! I am very sorry. I did not read this talk page before rewriting the article. Comments: Need methods for solving be listed here? Shouldn't they be in Maximum flow problem? Shouldn't also stuff about problems related to max flow, such as bipartite matching, be there? When you write multiple sources/sinks, do you mean a multi-commodity problem (only known polynomic solution is linear programming, or do you mean a problem where you can add a super-source and a super-sink, and solve with regular max flow? --- Nils Grimsmo 07:55, 10 January 2006 (UTC)
It's okay. You did most of what I outlined and had in mind anyway :) Note that I said "the new page might be structured like so," I intended for Maximum flow problem to be laid out the way it is now. Re: multiple sources/sinks: I was thinking of the simple super-source and super-sink. I agree that multicommodity flow problem should be a separate page.
Should it be multi-commodity flow with a hyphen or without? I am not an English expert, so I am not sure. In my native language (Norwegian) we don't use a hypen when concatenating words, but I think you do in English. Is this a special case because the word multi describes the word commodity? In Cormen et al. they write multicommodity flow without a hyphen. On NIST:DADS they write it with a hyphen. If I enter "multi-commodity" in Google, I get a 'Did you mean: "multicommodity"' spelling suggestion, even though the two spellings have approximately the same number of hits. Cormen et al. also write max-flow min-cut theorem with hyphens. Should this article be renamed to that? Again, I am not sure which is more correct, but I like it better with hyphens, as it shows which of the words "belong" toghether. -- Nils Grimsmo 14:26, 13 January 2006 (UTC)
Retrieved from "http://en.wikipedia.org../../../m/a/x/Talk%7EMax-flow_min-cut_theorem_8cc2.html"