281 citations · 677 across the 14 of their papers we have counts for
4 papers · 1 filter
Cut Tree Construction from Massive Graphs
Takuya Akiba, Yoichi Iwata, Yosuke Sameshima +2
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 tree…
Fractality of Massive Graphs: Scalable Analysis with Sketch-Based Box-Covering Algorithm
Takuya Akiba, Kenko Nakamura, Taro Takaguchi
Analysis and modeling of networked objects are fundamental pieces of modern data mining. Most real-world networks, from biological to social ones, are known to have common structur…
Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover
Takuya Akiba, Yoichi Iwata
We investigate the gap between theory and practice for exact branching algorithms. In theory, branch-and-reduce algorithms currently have the best time complexity for numerous impo…
Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Takuya Akiba, Yoichi Iwata, Yuichi Yoshida
We propose a new exact method for shortest-path distance queries on large-scale networks. Our method precomputes distance labels for vertices by performing a breadth-first search f…