Talk:Maximum flow problem

This  level-5 vital article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Computer science High‑importance This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles High This article has been rated as High-importance on the project's importance scale. Things you can help WikiProject Computer science with: Here are some tasks awaiting attention: Article requests : Requested articles/Applied arts and sciences/Computer science, computing, and Internet Cleanup : Computer science articles needing attention Computer science articles needing expert attention Copyedit : Computing Expand : Computer science Infobox : Computer science articles without infoboxes Maintain : Timeline of computing 2020–present Photo : Find pictures for the biographies of computer scientists (see List of computer scientists) Computing articles needing images Stubs : Computer science stubs Unreferenced : WikiProject Computer science/Unreferenced BLPs Project-related : Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}} Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles Mid This article has been rated as Mid-priority on the project's priority scale.

Fairness in car sharing (carpool) subsection mentions some equations and images, but those are missing. Iomartin (talk) 11:34, 20 July 2015 (UTC)[reply]

The picture MFP2.jpg is wrong and it is an erroneous plagiarism of a copyrighted picture: See [1] — Preceding unsigned comment added by 131.188.224.200 (talk) 09:53, 21 November 2011 (UTC)[reply]

i think this diagram is wrong it is doing the opposite to what is being described in the text Vin and vout should be swapped — Preceding unsigned comment added by Spartan3123 (talk • contribs) 00:50, 7 November 2011 (UTC)[reply]

I'd like to see some examples of problems that can be solved by turning them into Maximum flow problems. Joepnl (talk) 16:53, 8 October 2010 (UTC)[reply]

And what does it mean that there exists an integral maximum flow? Velle (talk) 23:57, 27 January 2011 (UTC)[reply]

It means that edge capacities and flow values are integers. -- X7q (talk) 01:05, 28 January 2011 (UTC)[reply]

The history section is severely flawed. The referenced papers do not support the claim that Dantzig created the max flow problem or that it was used in the Berlin airlift. The cited papers refers to the transportation problem. The referenced textbook (CLRS) does not acknowledge Dantzig as the creator of the max flow problem. The only reference to the Berlin airlift is an MIT press release (and its echos). I would view Schrijver's peer-reviewed article as authoritative.

Schrijver, Alexander, "On the history of the transportation and maximum flow problems", Mathematical Programming 91 (2002) 437-445

Moreover, the 2010 electric flow result is a significant result, but it is misleading to single it out in the history section (e.g., instead of Edmonds-Karp or other classic results). —Preceding unsigned comment added by 128.112.139.195 (talk) 10:36, 18 April 2011 (UTC)[reply]

First of all, the minimum path cover in DAG problem is not an application of max flow. It is an application of maximum bipartite matching and should be moved to that page. Also I believe it's better to express this application using Dilworth's theorem. — Preceding unsigned comment added by Mizgly (talk • contribs) 19:30, 5 December 2012 (UTC)[reply]

It is noteworthy to differentiate between a "path cover" and a "vertex-disjoint path cover". The current section only applies to the vertex-disjoint case. A counter-example being 1->2->4, 3->2->5. 141.3.49.88 (talk) 16:15, 27 April 2015 (UTC)[reply]

I removed the following example, as it is half-baked and makes reference to a non-existent figure. Perhaps someone could flesh it out and add it back in?

The problem exactly is that ${\displaystyle N}$ people are pooling a car for ${\displaystyle k}$ days. Each participant can choose if he participates on each day. We aim to fairly decide who will be driving on a given day.
The solution is the following:
We can decide this on the basis of the number of people using the car i.e.; if ${\displaystyle m}$ people use the car on a day, each person has a responsibility of ${\displaystyle 1/m}$. Thus, for every person ${\displaystyle i}$, his driving obligation ${\displaystyle D_{i}}$ as shown. Then person ${\displaystyle i}$ is required to drive only ${\displaystyle [D_{i}]}$ times in ${\displaystyle k}$ days.
Our aim is to find if such a setting is possible. For this we try to model the problem as a network.
Now, it can be proved that if a flow ${\displaystyle k}$ exists then such a fair setting exists and such a flow of value ${\displaystyle k}$ always exists.

Doctormatt (talk) 00:03, 28 August 2015 (UTC)[reply]

One should update the table that lists the best known algorithms for computing the maximum flow. To the best of my knowledge the best current algorithm is Madry's algorithm running in time O(m^(10/7) polylog(m)). The paper of the algorithm is called "Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back" and can be found here: https://people.csail.mit.edu/madry/docs/matching_flow.pdf --131.130.117.228 (talk) 17:04, 18 January 2016 (UTC)[reply]

Note however that Madry's algorithm only applies for networks with unit capacities. The table however is definitely missing the algorithm with running time O(m n^(1/2) polylog(n) log^2 U) by Lee and Sidford: https://arxiv.org/abs/1312.6713 (FOCS 2014). I'm not adding it myself right now because I do not know which method for writing polylog(n) in the running time is preferred by WP. In research papers we often use tilde-O notation, but it does not seem appropriate here. — Preceding unsigned comment added by 2001:628:2120:630:F1B4:3809:85FE:5DE (talk) 12:42, 11 January 2018 (UTC)[reply]

Hello fellow Wikipedians,

I have just modified one external link on Maximum flow problem. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf to http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 00:08, 23 January 2018 (UTC)[reply]

There are numerous issues with the subsection "Minimum path cover in directed acyclic graph" (besides no cited sources):

1. The terms "in-degree" and "out-degree" are not defined in this article, but if we assume they take the usual meaning – "positive out-degree" of ${\displaystyle v}$ means that there is one or more edges leaving ${\displaystyle v}$ – then ${\displaystyle V_{in}}$ and ${\displaystyle V_{out}}$ can be non-disjoint, which contradicts the statement that ${\displaystyle G'}$ is a bipartite graph. Although it can be understood that ${\displaystyle V_{in}}$ and ${\displaystyle V_{out}}$ contain "symbolic" vertices constituting the original vertices of ${\displaystyle V}$, such that the symbolic vertices for a certain ${\displaystyle v\in V}$ are distinct in ${\displaystyle V_{in}}$ and ${\displaystyle V_{out}}$, it is necessary to make this distinctness explicit, for example using a notation such as ${\displaystyle \{v_{\textrm {in}}\vert v\in V\land v{\text{ has positive in-degree}}\}}$.
2. Similarly, taking the current definition of ${\displaystyle V_{in}}$ and ${\displaystyle V_{out}}$, ${\displaystyle E'}$ simply equals ${\displaystyle E}$, since for each ${\displaystyle (u,v)\in E}$ it certainly holds that out-degree of ${\displaystyle u}$ and in-degree of ${\displaystyle v}$ are both positive. This again contradicts the statement that ${\displaystyle G'}$ is a bipartite graph, since ${\displaystyle V_{out}}$ and ${\displaystyle V_{in}}$ are in general not independent.
3. Kőnig's theorem relates vertex covers to matchings in bipartite graphs. It is not clear how one would use Kőnig's theorem to relate matchings in ${\displaystyle G'}$ to verex-disjoint path covers in ${\displaystyle G}$.
4. Overall, it is not clear whether and why are the observations in this section correct. As currently stated, it leaves too much room for interpretation and gives no intuitive explanation of the principle, althought the intuition is quite simple.

I would suggest either incorporating these remarks or removing the subsection. --84.245.120.59 (talk) 19:44, 21 November 2020 (UTC)[reply]