Gomory hu tree

[ArpitaHanjagi]

Algorithm: Gomory-Hu Tree

Purpose: Represents all-pairs minimum cuts in an undirected weighted graph as a tree.

Theory:

Each edge in the tree corresponds to a minimum cut between its endpoints.

Any min-cut between two vertices in the original graph is the minimum weight on the path connecting them in the tree.

Time Complexity: O(V * max-flow) (depends on the max-flow algorithm used).

Space Complexity: O(V + E).

Input: Weighted undirected graph as adjacency list.

Output: Parent array and edge weights representing the Gomory-Hu tree.

[github-actions[bot]]

This PR is stale because it has been open 30 days with no activity. Remove stale label or comment or this will be closed in 7 days.

[github-actions[bot]]

This PR was closed because it has been stalled for 7 days with no activity.