Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions

DOI10.1007/s00453-019-00658-6zbMath1433.68302OpenAlexW2996205869WikidataQ126588996 ScholiaQ126588996MaRDI QIDQ1987237

Charles Maske, Elias P. jun. Duarte, Jaime Cohen

Publication date: 14 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-019-00658-6

zbMATH Keywords

parallel algorithmsgraph contractionscut treesGomory-Hu algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Uses Software

• Pajek
• Pajek datasets
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implementing an efficient minimum capacity cut algorithm
• Statistical mechanics of complex networks
• Very Simple Methods for All Pairs Network Flow Analysis
• Cut Problems in Graphs with a Budget Constraint
• Algorithmic Aspects of Graph Connectivity
• Multi-Terminal Network Flows
• Finding k Cuts within Twice the Optimal
• Planar Graph Perfect Matching Is in NC
• New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
• Collective dynamics of ‘small-world’ networks

This page was built for publication: Speeding up the Gomory-Hu parallel cut tree algorithm with efficient graph contractions