The Gomory-Hu tree of an undirected graph with capacities is a weighted tree, studied in combinatorial optimization, that represents the minimum s-t cuts for every pair of vertices in the graph. It can be constructed using one fewer maximum-flow computation than the number of vertices in the graph, and it is named for Ralph E. Gomory and T. C. Hu.
Sources
Gomory-Hu tree (Wikipedia)
In Group: Network Flow and Matching Algorithms, LeadQuote, In Group: Network Flow and Matching Algorithms, 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.