Buchumschlag

Faster Weak Expander Decompositions and Approximate Max Flow

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Fleischmann, Henry, Li, George Z., Li, Jason
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Improved Directed Expander Decompositions
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

Fast Algorithms for Graph Arboricity and Related Problems
von: Cen, Ruoxu, et al.
Veröffentlicht: (2025)

On the Streaming Complexity of Expander Decomposition
von: Chen, Yu, et al.
Veröffentlicht: (2024)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
von: Dong, Sally, et al.
Veröffentlicht: (2023)

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Expander Decomposition with Almost Optimal Overhead
von: Bansal, Nikhil, et al.
Veröffentlicht: (2026)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
von: Li, Jason, et al.
Veröffentlicht: (2025)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Expander Decomposition for Non-Uniform Vertex Measures
von: Agassy, Daniel, et al.
Veröffentlicht: (2025)

Near-Optimal Algorithm for Directed Expander Decompositions
von: Sulser, Aurelio L., et al.
Veröffentlicht: (2024)

New Structures and Algorithms for Length-Constrained Expander Decompositions
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

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

Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
von: Agassy, Daniel, et al.
Veröffentlicht: (2022)

Approximating Directed Minimum Cut and Arborescence Packing via Directed Expander Hierarchies
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
von: Li, Jason
Veröffentlicht: (2025)

Deterministic Expander Routing: Faster and More Versatile
von: Chang, Yi-Jun, et al.
Veröffentlicht: (2024)

Bellman-Ford in Almost-Linear Time for Dense Graphs
von: Li, George Z., et al.
Veröffentlicht: (2026)

Faster Approximate Linear Matroid Intersection
von: Terao, Tatsuya
Veröffentlicht: (2026)

Faster Approximation Algorithms for k-Center via Data Reduction
von: Filtser, Arnold, et al.
Veröffentlicht: (2025)

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

Finding Colorings in One-Sided Expanders
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2025)

Expanderizing Higher Order Random Walks
von: Alev, Vedat Levi, et al.
Veröffentlicht: (2024)

Optimal Electrical Oblivious Routing on Expanders
von: Florescu, Cella, et al.
Veröffentlicht: (2024)

Faster Algorithms for Schatten-p Low Rank Approximation
von: Kacham, Praneeth, et al.
Veröffentlicht: (2024)

Faster Approximate Fixed Points of $\ell_\infty$-Contractions
von: Feodorov, Andrei, et al.
Veröffentlicht: (2026)

Shortcutting for Negative-Weight Shortest Path
von: Li, George Z., et al.
Veröffentlicht: (2025)

Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
von: Łącki, Jakub, et al.
Veröffentlicht: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

On Approximability of Steiner Tree in $\ell_p$-metrics
von: Fleischmann, Henry, et al.
Veröffentlicht: (2023)

Congestion-Approximators from the Bottom Up
von: Li, Jason, et al.
Veröffentlicht: (2024)

Reviving Thorup's Shortcut Conjecture
von: Bernstein, Aaron, et al.
Veröffentlicht: (2025)

Faster Algorithms for Fair Max-Min Diversification in $\mathbb{R}^d$
von: Kurkure, Yash, et al.
Veröffentlicht: (2024)

Worst-Case to Expander-Case Reductions: Derandomized and Generalized
von: Abboud, Amir, et al.
Veröffentlicht: (2024)

Local Sherman's Algorithm for Multi-commodity Flow
von: Li, Jason, et al.
Veröffentlicht: (2025)

Approximating Small Sparse Cuts
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Weakly Approximating Knapsack in Subquadratic Time
von: Chen, Lin, et al.
Veröffentlicht: (2025)

Unbreakable Decomposition in Close-to-Linear Time
von: Anand, Aditya, et al.
Veröffentlicht: (2024)