SpecializedSource checked

Gomory-Hu Tree

Gomory-Hu Tree addresses all-pairs minimum cuts by building a cut-equivalent tree from repeated minimum cut computations.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Advanced
Family: Graph Cuts
Tier: Specialized
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 5
Code example: Not ready
Visualization: Ready

Overview

Gomory-Hu Tree is a graph cuts method for all-pairs minimum cuts. It works by building a cut-equivalent tree from repeated minimum cut computations.

Core Concepts

all-pairs minimum cutsgraph cutsgraph traversal

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O((V + E) log V)

Worst

O(V^2 + E)

Space

O(V + E)

When to Use

Use Gomory-Hu Tree when solving all-pairs minimum cuts and you want to benefit from building a cut-equivalent tree from repeated minimum cut computations.
Choose it when O((V + E) log V) average/worst-case time and O(V + E) memory match your workload profile.
Prefer it over Push-Relabel or Capacity Scaling Max Flow when the problem structure favors all-pairs minimum cuts.

When Not to Use

Avoid when the graph model does not match the method's direction, weight, or connectivity assumptions.
Avoid when a simpler traversal gives the same information with less bookkeeping.

What It Does

Computes all-pairs minimum cuts within Graph Cuts workloads (O((V + E) log V) time, O(V + E) space).
Works by building a cut-equivalent tree from repeated minimum cut computations.
Maintains key invariants across all-pairs minimum cuts, graph cuts, graph traversal.

Use Cases

Production and research workloads requiring all-pairs minimum cuts via building a cut-equivalent tree from repeated minimum cut computations.
Graph Cuts pipelines where O((V + E) log V) time and O(V + E) space fit system constraints.
Engineering comparisons against Push-Relabel and Capacity Scaling Max Flow when tuning all-pairs minimum cuts.

Inputs

Undirected edge-weighted graph G = (V, E, w)

Outputs

Minimum cut value and vertex partition (S, V \ S) or cut-tree representation

Pseudocode

1.Construct the graph representation G = (V, E) and initialize auxiliary structures for all-pairs minimum cuts (graph cuts).
2.Seed the initial frontier, partition, or residual capacities according to Gomory-Hu Tree's invariants.
3.Iteratively process vertices or edges by building a cut-equivalent tree from repeated minimum cut computations.
4.Maintain structural invariants (all-pairs minimum cuts, graph cuts, graph traversal) and prune or contract resolved subproblems.
5.Extract and return the final all-pairs minimum cuts structure from the converged graph state.

Canonical Example

Input: Undirected edge-weighted graph G = (V, E, w) configured for a representative all-pairs minimum cuts test case
Output: Minimum cut value and vertex partition (S, V \ S) or cut-tree representation satisfying Gomory-Hu Tree invariants
Explanation: Gomory-Hu Tree processes the input by building a cut-equivalent tree from repeated minimum cut computations, tracking all-pairs minimum cuts and graph cuts to produce the verified all-pairs minimum cuts result.

Implementation Notes

Represent vertices and edges explicitly before optimizing storage.
Keep graph direction, weights, and multiedges clear in tests.
Record tie-breaking when multiple valid outputs exist.

Common Pitfalls

Using the method on the wrong graph type, such as directed versus undirected or weighted versus unweighted.
Forgetting disconnected components or isolated vertices.
Letting tie-breaking hide nondeterministic output in tests.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show building a cut-equivalent tree from repeated minimum cut computations on a small all-pairs minimum cuts example.

Step 1 of 5: Construct the graph representation G = (V, E) and initialize auxiliary structures for all-pairs minimum cuts (graph cuts).

graph-traversal-mechanism

Notes

Gomory-Hu Tree operates in O((V + E) log V) time and O(V + E) space within the Graph Cuts family. Often compared with Push-Relabel and Capacity Scaling Max Flow.