Cut Tree Construction from Massive Graphs

The construction of cut trees (also known as Gomory-Hu trees) for a given graph enables the minimum-cut size of the original graph to be obtained for any pair of vertices. Cut trees are a powerful back-end for graph management and mining, as they support various procedures related to the minimum cut...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-09
Main Authors: Akiba, Takuya, Iwata, Yoichi, Sameshima, Yosuke, Mizuno, Naoto, Yano, Yosuke
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Construction costs
Graph theory
Graphs
Timberlands
Trees
Trees (mathematics)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The construction of cut trees (also known as Gomory-Hu trees) for a given graph enables the minimum-cut size of the original graph to be obtained for any pair of vertices. Cut trees are a powerful back-end for graph management and mining, as they support various procedures related to the minimum cut, maximum flow, and connectivity. However, the crucial drawback with cut trees is the computational cost of their construction. In theory, a cut tree is built by applying a maximum flow algorithm for \(n\) times, where \(n\) is the number of vertices. Therefore, naive implementations of this approach result in cubic time complexity, which is obviously too slow for today's large-scale graphs. To address this issue, in the present study, we propose a new cut-tree construction algorithm tailored to real-world networks. Using a series of experiments, we demonstrate that the proposed algorithm is several orders of magnitude faster than previous algorithms and it can construct cut trees for billion-scale graphs.
ISSN:2331-8422