Editing Flow network (section)

==Classifying flow problems==

The simplest and most common problem using flow networks is to find what is called the [[maximum flow]], which provides the largest possible total flow from the source to the sink in a given graph. There are many other problems which can be solved using max flow algorithms, if they are appropriately modeled as flow networks, such as [[bipartite matching]], the [[assignment problem]] and the [[transportation problem]]. Maximum flow problems can be solved in [[polynomial time]] with various algorithms (see table). The [[max-flow min-cut theorem]] states that finding a maximal network flow is equivalent to finding a  [[Cut (graph theory)|cut]] of minimum capacity that separates the source and the sink, where a cut is the division of vertices such that the source is in one division and the sink is in another.

{| class="wikitable" style="height: 200px;" align="right"
|+ Well-known algorithms for the Maximum Flow Problem
|-
! Inventor(s) || Year || Time<br/>complexity<br/>(with {{math|''n''}} nodes<br/>and {{math|''m''}} arcs)
|-
| [[Dinic's algorithm]] || 1970 || {{math|''O''(''mn''<sup>2</sup>)}}
|-
| [[Edmonds–Karp algorithm]] || 1972 || {{math|''O''(''m''<sup>2</sup>''n'')}}
|-
| |MPM (Malhotra, Pramodh-Kumar, and Maheshwari)<br/>algorithm<ref>{{Cite journal| last1 = Malhotra| first1 = V.M.| last2 = Kumar| first2 = M.Pramodh| last3 = Maheshwari| first3 = S.N.| doi = 10.1016/0020-0190(78)90016-9| title = An <math>O(|V|^3)</math> algorithm for finding maximum flows in networks| journal = Information Processing Letters| volume = 7| issue = 6| pages = 277–278| year = 1978| url = https://eprints.utas.edu.au/160/1/iplFlow.pdf| access-date = 2019-07-11| archive-date = 2021-04-18| archive-url = https://web.archive.org/web/20210418071844/https://eprints.utas.edu.au/160/1/iplFlow.pdf| url-status = live}}</ref>
  ||  1978 || {{math|''O''(''n''<sup>3</sup>)}}
|-
| [[Push–relabel algorithm]] ([[Andrew V. Goldberg|Goldberg]] & [[Robert Tarjan|Tarjan]]) || 1988  || {{math|''O''(''n''<sup>2</sup>''m'')}}

|-
| [[James B. Orlin]]<ref>{{Cite book|last=Orlin|first=James B.|title=Proceedings of the forty-fifth annual ACM symposium on Theory of Computing |chapter=Max flows in O(nm) time, or better |date=2013-06-01|chapter-url=https://doi.org/10.1145/2488608.2488705|series=STOC '13|location=Palo Alto, California, USA|publisher=Association for Computing Machinery|pages=765–774|doi=10.1145/2488608.2488705|isbn=978-1-4503-2029-0|via=|hdl=1721.1/88020|s2cid=207205207|hdl-access=free}}</ref>|| 2013 || {{math|''O''(''mn'')}}
|-
|Li Chen, Rasmus Kyng, Yang P. Liu, 
Richard Peng, Maximilian Probst Gutenberg,
Sushant Sachdeva
|2022
|<math>O(m^{1+o(1)})</math>
|}

In a [[multi-commodity flow problem]], you have multiple sources and sinks, and various "commodities" which are to flow from a given source to a given sink. This could be for example various goods that are produced at various factories, and are to be delivered to various given customers through the ''same'' transportation network.

In a [[minimum cost flow problem]], each edge <math>u,v</math> has a given cost <math>k(u,v)</math>, and the cost of sending the flow <math>f(u,v)</math> across the edge is <math>f(u,v) \cdot k(u,v)</math>. The objective is to send a given amount of flow from the source to the sink, at the lowest possible price.

In a [[circulation problem]], you have a lower bound <math>\ell(u,v)</math> on the edges, in addition to the upper bound <math>c(u,v)</math>. Each edge also has a cost. Often, flow conservation holds for ''all'' nodes in a circulation problem, and there is a connection from the sink back to the source. In this way, you can dictate the total flow with <math>\ell(t,s)</math> and <math>c(t,s)</math>. The flow ''circulates'' through the network, hence the name of the problem.

In a '''network with gains''' or '''generalized network''' each edge has a '''[[gain graph|gain]]''', a real number (not zero) such that, if the edge has gain ''g'', and an amount ''x'' flows into the edge at its tail, then an amount ''gx'' flows out at the head.

In a '''source localization problem''', an algorithm tries to identify the most likely source node of information diffusion through a partially observed network. This can be done in linear time for trees and cubic time for arbitrary networks and has applications ranging from tracking mobile phone users to identifying the originating source of disease outbreaks.<ref>{{Cite journal| last1 =Pinto| first1 =P.C.| last2 =Thiran| first2 =P.| last3 =Vetterli| first3 =M.| date =2012| title =Locating the source of diffusion in large-scale networks| url =http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf| journal =Physical Review Letters| volume =109| issue =6| page =068702| doi =10.1103/PhysRevLett.109.068702| pmid =23006310| arxiv =1208.2534| bibcode =2012PhRvL.109f8702P| s2cid =14526887| access-date =2012-08-14| archive-date =2012-10-22| archive-url =https://web.archive.org/web/20121022084454/http://www.pedropinto.org.s3.amazonaws.com/publications/locating_source_diffusion_networks.pdf| url-status =live}}</ref>