Buchumschlag

New Structures and Algorithms for Length-Constrained Expander Decompositions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Haeupler, Bernhard, Hershkowitz, D Ellis, Tan, Zihan
Format:	Preprint
Veröffentlicht:	2024
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

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, 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)

Simple Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2024)

Planar Length-Constrained Minimum Spanning Trees
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2025)

Low-Step Multi-Commodity Flow Emulators
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

A Cut-Matching Game for Constant-Hop Expanders
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2022)

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

Near-Optimal Directed Low-Diameter Decompositions
von: Bringmann, Karl, et al.
Veröffentlicht: (2025)

Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Maintaining Random Assignments under Adversarial Dynamics
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Ghost Value Augmentation for $k$-Edge-Connectivity
von: Hershkowitz, D Ellis, et al.
Veröffentlicht: (2023)

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

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

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

The Steiner Path Aggregation Problem
von: Chen, Da Qi, et al.
Veröffentlicht: (2025)

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

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

DAG Projections: Reducing Distance and Flow Problems to DAGs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Faster Weak Expander Decompositions and Approximate Max Flow
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

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

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

A Constant-Approximation Distance Labeling Scheme under Polynomially Many Edge Failures
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

Improved Parallel Algorithms for EF1 Allocations
von: Gowda, Kishen N, et al.
Veröffentlicht: (2026)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

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)

Maintaining Routing Structures under Deletions via Self-Pruning
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

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

Efficient Centroid-Linkage Clustering
von: Bateni, MohammadHossein, et al.
Veröffentlicht: (2024)

Dynamic Construction of the Lovász Local Lemma
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2026)

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)

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)

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

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
von: Abboud, Amir, et al.
Veröffentlicht: (2023)

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

An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
von: Sanaullah, Ahsan, et al.
Veröffentlicht: (2025)