Copertina

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Gutenberg, Maximilian Probst, Kyng, Rasmus, Yuan, Weixuan, Yuan, Wuwei
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
di: Gutenberg, Maximilian Probst, et al.
Pubblicazione: (2025)

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

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

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

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

A Simple Dynamic Spanner via APSP
di: Kyng, Rasmus, et al.
Pubblicazione: (2024)

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

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

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

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

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

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

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

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

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

Acceleration for Distributed Transshipment and Parallel Maximum Flow
di: Grunau, Christoph, et al.
Pubblicazione: (2025)

Bootstrapping Dynamic APSP via Sparsification
di: Kyng, Rasmus, et al.
Pubblicazione: (2024)

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

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
di: Adil, Deeksha, et al.
Pubblicazione: (2024)

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

A Simple and Fast Algorithm for Fair Cuts
di: Li, Jason, et al.
Pubblicazione: (2024)

Iterative Refinement for $\ell_p$-norm Regression
di: Adil, Deeksha, et al.
Pubblicazione: (2019)

Noisy (Binary) Searching: Simple, Fast and Correct
di: Dereniowski, Dariusz, et al.
Pubblicazione: (2021)

Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation
di: Pham, Ninh, et al.
Pubblicazione: (2025)

Sparse Suffix and LCP Array: Simple, Direct, Small, and Fast
di: Ayad, Lorraine A. K., et al.
Pubblicazione: (2023)

Fast Answering Pattern-Constrained Reachability Queries with Two-Dimensional Reachability Index
di: Yang, Huihui, et al.
Pubblicazione: (2025)

Simple Length-Constrained Minimum Spanning Trees
di: Hershkowitz, D Ellis, et al.
Pubblicazione: (2024)

Fast and Simple Densest Subgraph with Predictions
di: Bui, Thai, et al.
Pubblicazione: (2025)

Fast and Efficient Parallel Breadth-First Search with Power-law Graph Transformation
di: Jiang, Zite, et al.
Pubblicazione: (2020)

Fast and Simple $(1+ε)Δ$-Edge-Coloring of Dense Graphs
di: Dhawan, Abhishek
Pubblicazione: (2024)

A Simple 4-Approximation Algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees
di: Dempsey, Jordan, et al.
Pubblicazione: (2024)

A Simple and Fast $(3+\varepsilon)$-approximation for Constrained Correlation Clustering
di: Veldt, Nate
Pubblicazione: (2025)

A Simple Analysis of Ranking in General Graphs
di: Derakhshan, Mahsa, et al.
Pubblicazione: (2025)

A Simple Algorithm for Trimmed Multipoint Evaluation
di: Fischer, Nick, et al.
Pubblicazione: (2025)

A Simple Algorithm for Clustering Discrete Distributions
di: Mitra, Pradipta
Pubblicazione: (2026)

A Simple Algorithm for Dynamic Carpooling with Recourse
di: Efron, Yuval, et al.
Pubblicazione: (2024)

Simple Grid Polygon Online Exploration Revisited
di: Brock, Maximilian, et al.
Pubblicazione: (2024)

Simple and Faster Algorithms for Knapsack
di: He, Qizheng, et al.
Pubblicazione: (2023)

Partition-based Simple Heaps
di: Brodal, Gerth Stølting, et al.
Pubblicazione: (2026)

Fast exact algorithms via the Matrix Tree Theorem
di: Arvind, V., et al.
Pubblicazione: (2025)