High-speed minimum cut approximation in dense graph using compacted pruned tree

DOI10.1002/MMA.11165MaRDI QIDQ6928210zbMATH OpenFDO

Authors Ronghua Ma, Weibin Yao

Publication date 17 September 2025

Published in Mathematical Methods in the Applied Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/MMA.11165

zbMATH Keywords

algorithm accelerationapproximate algorithmdepth-first traversalminimum cuttree compacting

Mathematics Subject Classification ID

General and overarching topics; collections (00-XX)

Cites work

• A nearly optimal all-pairs min-cuts algorithm in simple graphs
• A simple deterministic algorithm for edge connectivity
• A simple min-cut algorithm
• Cut-equivalent trees are optimal for min-cut queries
• Deterministic min-cut in poly-logarithmic max-flows
• Deterministic mincut in almost-linear time
• Distributed weighted min-cut in nearly-optimal time
• Faster cut-equivalent trees in simple graphs
• Graph theory
• Minimum cut in O(m^2 n time
• Multi-Terminal Network Flows
• Simplifying maximum flow computations: the effect of shrinking and good initial flows
• Speed scaling on parallel processors with migration
• Universally-Optimal Distributed Exact Min-Cut
• Very Simple Methods for All Pairs Network Flow Analysis

This page was built for publication: High-speed minimum cut approximation in dense graph using compacted pruned tree

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