Algorithms for moving the most flow through a network or pairing vertices of a graph, such as Edmonds-Karp, Dinic's algorithm, the Hopcroft-Karp algorithm, the Hungarian algorithm, the blossom algorithm and the Gale-Shapley algorithm. An algorithm belongs here when its cited article describes maximum flow, matching or assignment. It excludes shortest path and spanning tree algorithms. A member is placed here by what its own cited article states about it, not by the name of the algorithm or by the uses it is put to today, so each entry sits in the group its source describes it as belonging to.
Browse By
Network Flow and Matching Algorithms
Filter Results9 entries
Sources
Wikipedia: Edmonds-Karp Algorithm
Wikimedia FoundationHas Member: Edmonds-Karp Algorithm, Lead sectionQuote, Has Member: Edmonds-Karp Algorithm, Lead section
computing the maximum flow in a flow network
Dinic's Algorithm (Wikipedia)
Has Member: Dinic's Algorithm, Lead sectionQuote, Has Member: Dinic's Algorithm, Lead section
computing the maximum flow in a flow network
Hungarian Algorithm (Wikipedia)
Has Member: Hungarian Algorithm, Lead sectionQuote, Has Member: Hungarian Algorithm, Lead section
solves the assignment problem in polynomial time
Blossom algorithm (Wikipedia)
Has Member: Blossom Algorithm, Lead sectionQuote, Has Member: Blossom Algorithm, Lead section
constructing maximum matchings on graphs
Push-relabel maximum flow algorithm (Wikipedia)
Has Member: Push-Relabel Algorithm, Lead sectionQuote, Has Member: Push-Relabel Algorithm, Lead section
is an algorithm for computing maximum flows in a flow network
Wikipedia: Hopcroft-Karp algorithm
Has Member: Hopcroft-Karp Algorithm, LeadQuote, Has Member: Hopcroft-Karp Algorithm, Lead
In computer science, the Hopcroft-Karp algorithm (sometimes more accurately called the Hopcroft-Karp-Karzanov algorithm) is an algorithm that takes a bipartite graph as input and produces a maximum-cardinality matching as output, a set of as many edges as possible with the property that no two edges share an endpoint.
Stoer-Wagner algorithm (Wikipedia)
Has Member: Stoer-Wagner Algorithm, LeadQuote, Has Member: Stoer-Wagner Algorithm, Lead
In graph theory, the Stoer-Wagner algorithm is a recursive algorithm to solve the minimum cut problem in undirected weighted graphs with non-negative weights.
Gale-Shapley algorithm (Wikipedia)
Has Member: Gale-Shapley Algorithm, LeadQuote, Has Member: Gale-Shapley Algorithm, Lead
In mathematics, economics, and computer science, the Gale-Shapley algorithm (also known as the deferred acceptance algorithm, propose-and-reject algorithm, or Boston Pool algorithm) is an algorithm for finding a solution to the stable matching problem.
Gomory-Hu tree (Wikipedia)
Has Member: Gomory-Hu Tree Algorithm, LeadQuote, Has Member: Gomory-Hu Tree Algorithm, Lead
The Gomory-Hu tree can be constructed in |V| − 1 maximum flow computations.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.