Cover Image

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Daoyuan, Meierhans, Simon, Gutenberg, Maximilian Probst, Saranurak, Thatchaphol
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

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

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

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

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

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
by: Gutenberg, Maximilian Probst, et al.
Published: (2025)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Approximating Small Sparse Cuts
by: Anand, Aditya, et al.
Published: (2024)

Chasing Positive Bodies
by: Bhattacharya, Sayan, et al.
Published: (2023)

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

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

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