Cover Image

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Haeupler, Bernhard, Roeyskoe, Antti, Zhang, Zhijun
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Maintaining Routing Structures under Deletions via Self-Pruning
by: Haeupler, Bernhard, et al.
Published: (2025)

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

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

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

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

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

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

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

Diameter Shortcut Sets on Temporal Graphs
by: Quantmeyer, Gerome
Published: (2025)

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

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

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

Dynamic Construction of the Lovász Local Lemma
by: Haeupler, Bernhard, et al.
Published: (2026)

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

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

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

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

Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
by: Duraj, Lech, et al.
Published: (2023)

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

A Branch-and-Bound Approach for Maximum Low-Diameter Dense Subgraph Problems
by: Zhou, Yi, et al.
Published: (2025)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., et al.
Published: (2025)

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

Shortcuts and Transitive-Closure Spanners Approximation
by: Chalermsook, Parinya, et al.
Published: (2025)

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

Diameter Computation on (Random) Geometric Graphs
by: Bläsius, Thomas, et al.
Published: (2026)

Going Beyond Surfaces in Diameter Approximation
by: Włodarczyk, Michał
Published: (2025)

Fault-Tolerant ST-Diameter Oracles
by: Bilò, Davide, et al.
Published: (2023)

Streaming Diameter of High-Dimensional Points
by: Halldórsson, Magnús M., et al.
Published: (2025)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Tight Better-Than-Worst-Case Bounds for Element Distinctness and Set Intersection
by: van der Hoog, Ivor, et al.
Published: (2025)

An Optimal Algorithm for Cardinality-Constrained Diameter Partitioning
by: Xu, Chao, et al.
Published: (2026)

FPT approximations for Capacitated Sum of Radii and Diameters
by: Filtser, Arnold, et al.
Published: (2024)

Simpler and Faster Directed Low-Diameter Decompositions
by: Li, Jason
Published: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
by: Bernstein, Aaron, et al.
Published: (2022)

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults
by: Parter, Merav, et al.
Published: (2024)

Clustering with Label Consistency
by: Chakraborty, Diptarka, et al.
Published: (2025)

New Diameter Approximations via Distance Oracle Techniques
by: Kirkpatrick, Yael, et al.
Published: (2026)

Log Diameter Rounds MST Verification and Sensitivity in MPC
by: Coy, Sam, et al.
Published: (2024)

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

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)