Cover Image

Simple Length-Constrained Expander Decompositions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodwin, Greg, Haeupler, Bernhard, Hershkowitz, D Ellis, Tan, Zihan
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

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

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

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

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

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

Multiplicative Spanners in Minor-Free Graphs
by: Bodwin, Greg, et al.
Published: (2025)

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

Improved Online Reachability Preservers
by: Bodwin, Greg, et al.
Published: (2024)

A Lower Bound for Light Spanners in General Graphs
by: Bodwin, Greg, et al.
Published: (2024)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

A Cut-Matching Game for Constant-Hop Expanders
by: Haeupler, Bernhard, et al.
Published: (2022)

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

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

An Alternate Proof of Near-Optimal Light Spanners
by: Bodwin, Greg
Published: (2023)

Notes on the Linear Algebraic View of Regularity Lemmas
by: Bodwin, Greg, et al.
Published: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
by: Bodwin, Greg, et al.
Published: (2026)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
by: Bodwin, Greg, et al.
Published: (2023)

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

Maintaining Random Assignments under Adversarial Dynamics
by: Haeupler, Bernhard, et al.
Published: (2026)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Ghost Value Augmentation for $k$-Edge-Connectivity
by: Hershkowitz, D Ellis, et al.
Published: (2023)

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)

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

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

The Steiner Path Aggregation Problem
by: Chen, Da Qi, et al.
Published: (2025)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
by: Fischer, Nick, et al.
Published: (2024)

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

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

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

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

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

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

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

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

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
by: Bodwin, Greg, et al.
Published: (2022)

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

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
by: Bodwin, Greg, et al.
Published: (2024)

The Discrepancy of Shortest Paths
by: Bodwin, Greg, et al.
Published: (2024)

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