Buchumschlag

Near-Optimal Directed Low-Diameter Decompositions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bringmann, Karl, Fischer, Nick, Haeupler, Bernhard, Latypov, Rustam
Format:	Preprint
Veröffentlicht:	2025
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

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

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)

Length-Constrained Directed Expander Decomposition and Length-Constrained Vertex-Capacitated Flow Shortcuts
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

Knapsack with Small Items in Near-Quadratic Time
von: Bringmann, Karl
Veröffentlicht: (2023)

Beating Bellman's Algorithm for Subset Sum
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
von: Li, Jason
Veröffentlicht: (2025)

New Structures and Algorithms for Length-Constrained Expander Decompositions
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2024)

Efficiently Listing Projected Trees, and Equivalence of Listing and Enumeration
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

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

Simple Length-Constrained Expander Decompositions
von: Bodwin, Greg, et al.
Veröffentlicht: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
von: Li, Jason, et al.
Veröffentlicht: (2025)

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

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

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

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

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

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

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

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2026)

A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

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

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

Adaptive Massively Parallel Coloring in Sparse Graphs
von: Latypov, Rustam, et al.
Veröffentlicht: (2024)

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
von: Bringmann, Karl, et al.
Veröffentlicht: (2022)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
von: Bringmann, Karl, et al.
Veröffentlicht: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

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

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
von: Xu, Chao, et al.
Veröffentlicht: (2026)

On Strong Diameter Padded Decompositions
von: Filtser, Arnold
Veröffentlicht: (2019)

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

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

Lawler-Moore Speedups via Additive Combinatorics
von: Bringmann, Karl, et al.
Veröffentlicht: (2026)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
von: Fischer, Nick
Veröffentlicht: (2026)

Sumsets, 3SUM, Subset Sum: Now for Real!
von: Fischer, Nick
Veröffentlicht: (2024)

Polyline Simplification has Cubic Complexity
von: Bringmann, Karl, et al.
Veröffentlicht: (2018)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2021)

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

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
von: Zhou, Yi, et al.
Veröffentlicht: (2025)

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