Simpler and Faster Directed Low-Diameter Decompositions

2025/05/15 by Jason Li, Li, Jason · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Polynomial and algebraic computation #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2505.10244

openalex publication_date 2025/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a simpler and faster algorithm for low-diameter decompositions on directed graphs, matching the O(log nloglog n) loss factor from Bringmann, Fischer, Haeupler, and Latypov (ICALP 2025) and improving the running time to O((m+nloglog n)log²n).

Citations

• Near-Optimal Directed Low-Diameter Decompositions
• Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
• Negative-Weight Single-Source Shortest Paths in Near-linear Time
• Parallel Graph Decompositions Using Random Shifts
• Near Linear-Work Parallel SDD Solvers, Low-Diameter Decomposition, and\n Low-Stretch Subgraphs
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Cited by

• Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation

Related

• Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
• Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
• Near-Optimal Directed Low-Diameter Decompositions
• Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
• Short Cycles via Low-Diameter Decompositions