Everything about Flow network
Directed graph where edges have a capacity
In graph theory, a flow network or a transportation network is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations research, a directed graph is called a network, the vertices are called nodes and the edges are called arcs. A flow must satisfy the restriction that the amount of flow into a node equals the amount of flow out of it, unless it is a source, which has only outgoing flow, or sink, which has only incoming flow. A flow network can be used to model traffic in a computer network, circulation with demands, fluids in pipes, currents in an electrical circuit, or anything similar in which something travels through a network of nodes. As such, efficient algorithms for solving network flows can also be applied to solve problems that can be reduced to a flow network, including survey design, airline scheduling, image segmentation, and the matching problem. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Flow networkA 5-minute orientation
- Skim a recent paper: Computing the Reliability of a Multistate Flow Network with Flow Loss EffectInfluential work since 2022
- Pick up a classic book: Jurisdiction and the InternetThe most-reprinted book on the subject
- Read the landmark paper: Network information flowCited 6,405 times
- Go sideways: Push–relabel maximum flow algorithmA closely related topic
- Go sideways: Ford–Fulkerson algorithmA closely related topic
đź“– Definitions
Noun A directed graph where each edge has a capacity and each edge receives a flow.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Network information flow
Centrality and network flow
Maximal Flow Through a Network
Flow in porous media — pore-network models and multiphase flow
Network Autocorrelation in Transport Network and Flow Systems
Network flow analysis algorithms
Pore-network modeling of flow in shale nanopores: Network structure, flow principles, and computational algorithms
Network Flow Watermarking: A Survey
🆕 Influential since 2022
đź“š Books worth reading
Jurisdiction and the InternetUta Kohl · 2007
Borders in cyberspaceBrian Kahin, Charles R. Nesson · 1996
Introduction to distribution logisticsPaolo Brandimarte, Giulio Zotteri · 2007
Index and Query Methods in Road NetworksJun Feng, Toyohide Watanabe · 2014
Flow control in computer networksInternational Symposium on Flow Control in Computer Networks Versailles 1979. · 1979
Congestion Control In Data Transmission Networks Sliding Mode And Other DesignsAndrzej Bartoszewicz, Przemysław Ignaciuk · 2012
Climate variability and change--hydrological impactsFRIEND 2006 (2006 Havana, Cuba) · 2006
FRIEND 2002International Conference on FRIEND (4th 2002 Cape Town, South Africa), Henry A.J. van Lanen · 2002
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Push–relabel maximum flow algorithm In mathematical optimization, the push–relabel algorithm (alternatively, preflow–push algorithm) is an algorithm for computing maximum flows in a flow…
- Ford–Fulkerson algorithm The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network. It is sometimes called…
- Edmonds–Karp algorithm In computer science, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O(|V||E|2)…
- Max-flow min-cut theorem In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source…
- Minimum-cost flow problem The minimum-cost flow problem (MCFP) is an optimization and decision problem to find the cheapest possible way of sending a certain amount of flow through…
- Maximum flow problem In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate. The maximum…
- Suurballe's algorithm In theoretical computer science and network routing, Suurballe's algorithm is an algorithm for finding two disjoint paths in a nonnegatively-weighted directed…
- Circulation problem The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with…