Imagen de Portada

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Haeupler, Bernhard, Long, Yaowei, Saranurak, Thatchaphol, Wang, Shengzhe
Formato:	Preprint
Publicado:	2025
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
por: Haeupler, Bernhard, et al.
Publicado: (2025)

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

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

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Connectivity Oracle Under Vertex Failures by Shortcutting Unbreakable Decomposition
por: Li, Xizhe, et al.
Publicado: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
por: Haeupler, Bernhard, et al.
Publicado: (2025)

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

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
por: Haeupler, Bernhard, et al.
Publicado: (2026)

DAG Projections: Reducing Distance and Flow Problems to DAGs
por: Haeupler, Bernhard, et al.
Publicado: (2026)

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

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
por: Haeupler, Bernhard, et al.
Publicado: (2025)

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

Low-Step Multi-Commodity Flow Emulators
por: Haeupler, Bernhard, et al.
Publicado: (2024)

Unbreakable Decomposition in Close-to-Linear Time
por: Anand, Aditya, et al.
Publicado: (2024)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
por: Haeupler, Bernhard, et al.
Publicado: (2025)

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

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

Space Complexity of Vertex Connectivity Oracles
por: Pettie, Seth, et al.
Publicado: (2022)

Local Sherman's Algorithm for Multi-commodity Flow
por: Li, Jason, et al.
Publicado: (2025)

All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs
por: Anand, Aditya, et al.
Publicado: (2025)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
por: Bernstein, Aaron, et al.
Publicado: (2025)

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

Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
por: Jiang, Yonggang, et al.
Publicado: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
por: Anand, Aditya, et al.
Publicado: (2024)

Finding Most Shattering Minimum Vertex Cuts of Polylogarithmic Size in Near-Linear Time
por: Hua, Kevin, et al.
Publicado: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
por: Adil, Deeksha, et al.
Publicado: (2024)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
por: Haeupler, Bernhard, et al.
Publicado: (2026)

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

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

Near-Optimal Directed Low-Diameter Decompositions
por: Bringmann, Karl, et al.
Publicado: (2025)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
por: Bernstein, Aaron, et al.
Publicado: (2024)

Improved Directed Expander Decompositions
por: Fleischmann, Henry, et al.
Publicado: (2025)

Planar Length-Constrained Minimum Spanning Trees
por: Hershkowitz, D Ellis, et al.
Publicado: (2025)

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

Cactus Representation of Minimum Cuts: Derandomize and Speed up
por: He, Zhongtian, et al.
Publicado: (2024)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
por: Bernstein, Aaron, et al.
Publicado: (2025)

Chasing Positive Bodies
por: Bhattacharya, Sayan, et al.
Publicado: (2023)

Approximating Small Sparse Cuts
por: Anand, Aditya, et al.
Publicado: (2024)