Premium
Efficient algorithms for generalized cut‐trees
Author(s) -
Gusfield Dan,
Naor Dalit
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210503
Subject(s) - minimum cut , mathematics , combinatorics , undirected graph , maximum cut , enhanced data rates for gsm evolution , computation , tree (set theory) , node (physics) , directed graph , graph , discrete mathematics , algorithm , computer science , artificial intelligence , structural engineering , engineering
The Gomory–Hu cut tree is a compact and efficiently computed representation of selected minimum edge cuts in a weighted undirected graph G = (V, E) with n nodes. It represents ( n 2 ) minimum cuts, one for each pair of nodes in G , and can be constructed with only n − 1 flow computations. In this article, we generalize the types of cut‐trees that can be efficiently constructed. We solve the open problem, posed by Hu [9], of constructing with n − 1 flows a cut‐tree for minimum node weighted cuts in an undirected graph. We then show how to build cut‐trees that compactly represent the minimum edge cuts in directed graphs, partially solving the open problem of constructing cut‐trees for weighted edge cuts in directed graphs.