Cover Image

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gutenberg, Maximilian Probst, Yuan, Weixuan
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
by: Abboud, Amir, et al.
Published: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
by: Sulser, Aurelio L., et al.
Published: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
by: Chen, Daoyuan, et al.
Published: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Optimal Electrical Oblivious Routing on Expanders
by: Florescu, Cella, et al.
Published: (2024)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
by: Meierhans, Simon, et al.
Published: (2025)

Differentially Private Gomory-Hu Trees
by: Aamand, Anders, et al.
Published: (2024)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
by: Kyng, Rasmus, et al.
Published: (2025)

A computational study of Gomory-Hu construction tree algorithms
by: Kolmogorov, Vladimir
Published: (2022)

OrderedCuts: A new approach for computing Gomory-Hu tree
by: Kolmogorov, Vladimir
Published: (2022)

Simple Length-Constrained Expander Decompositions
by: Bodwin, Greg, et al.
Published: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
by: Das, Debarati, et al.
Published: (2026)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
by: Ashvinkumar, Vikrant, et al.
Published: (2026)

An Approximation Algorithm for Graph Label Selection
by: John, Josia, et al.
Published: (2026)

Improved Directed Expander Decompositions
by: Fleischmann, Henry, et al.
Published: (2025)

On the Streaming Complexity of Expander Decomposition
by: Chen, Yu, et al.
Published: (2024)

Expander Decomposition with Almost Optimal Overhead
by: Bansal, Nikhil, et al.
Published: (2026)

Expander Decomposition for Non-Uniform Vertex Measures
by: Agassy, Daniel, et al.
Published: (2025)

Faster Weak Expander Decompositions and Approximate Max Flow
by: Fleischmann, Henry, et al.
Published: (2025)

New Structures and Algorithms for Length-Constrained Expander Decompositions
by: Haeupler, Bernhard, et al.
Published: (2024)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
by: Abboud, Amir, et al.
Published: (2024)

Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
by: Bucić, Matija, et al.
Published: (2025)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
by: Brand, Jan van den, et al.
Published: (2024)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
by: Haeupler, Bernhard, et al.
Published: (2025)

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
by: Agassy, Daniel, et al.
Published: (2022)

Reviving Thorup's Shortcut Conjecture
by: Bernstein, Aaron, et al.
Published: (2025)

Deterministic Expander Routing: Faster and More Versatile
by: Chang, Yi-Jun, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Expander Hierarchies for Normalized Cuts on Graphs
by: Hanauer, Kathrin, et al.
Published: (2024)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

Breaking the $n^{1.5}$ Additive Error Barrier for Private and Efficient Graph Sparsification via Private Expander Decomposition
by: Aamand, Anders, et al.
Published: (2025)

Finding Colorings in One-Sided Expanders
by: Buhai, Rares-Darius, et al.
Published: (2025)

Expanderizing Higher Order Random Walks
by: Alev, Vedat Levi, et al.
Published: (2024)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
by: Elkin, Michael, et al.
Published: (2024)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
by: Das, Debarati, et al.
Published: (2025)

Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
by: Long, Yaowei, et al.
Published: (2024)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
by: Cruciani, Emilio, et al.
Published: (2025)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
by: Jiang, Yonggang, et al.
Published: (2025)

Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
by: Jeronimo, Fernando Granha, et al.
Published: (2022)