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

DOI10.1007/S00453-019-00658-6MaRDI QIDQ1987237zbMATH OpenOpenAlexWikidataFDO

Authors Charles Maske, Jaime Cohen, Elias P. Duarte

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

cut treesGomory-Hu algorithmgraph contractionsparallel algorithms

Mathematics Subject Classification ID

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

Recommendations

• Efficient algorithms for generalized cut‐trees
• Very Simple Methods for All Pairs Network Flow Analysis
• scientific article; zbMATH DE number 1305427
• Practical minimum cut algorithms
• Fast and simple fully-dynamic cut tree construction

Cites work

• Algorithmic Aspects of Graph Connectivity
• Collective dynamics of `small-world' networks
• Cut Problems in Graphs with a Budget Constraint
• Finding k Cuts within Twice the Optimal
• scientific article; zbMATH DE number 2084315 (Why is no real title available?)
• scientific article; zbMATH DE number 1305427 (Why is no real title available?)
• scientific article; zbMATH DE number 6472607 (Why is no real title available?)
• Implementing an efficient minimum capacity cut algorithm
• Multi-Terminal Network Flows
• New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
• Planar graph perfect matching is in NC
• Random graphs.
• Statistical mechanics of complex networks
• Very Simple Methods for All Pairs Network Flow Analysis

Cited in

(3)

• Cut tree algorithms: An experimental study
• scientific article; zbMATH DE number 1305427 (Why is no real title available?)
• Fast and simple fully-dynamic cut tree construction

Describes a project that uses

Uses Software

• Pajek
• Pajek datasets
• DIMACS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1987237)