Cover Image

Faster negative length shortest paths by bootstrapping hop reducers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Huang, Yufan, Jin, Peter, Quanrud, Kent
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Approximating Directed Connectivity in Almost-Linear Time
by: Quanrud, Kent
Published: (2025)

From Hop Reduction to Sparsification for Negative Length Shortest Paths
by: Quanrud, Kent, et al.
Published: (2025)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Faster shortest-path algorithms using the acyclic-connected tree
by: Stefansson, Elis, et al.
Published: (2025)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Solving the all pairs shortest path problem after minor update of a large dense graph
by: Liu, Gangli
Published: (2024)

Faster run-length compressed suffix arrays
by: Brown, Nathaniel K., et al.
Published: (2024)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
by: Kasperski, Adam, et al.
Published: (2024)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Finding longer cycles via shortest colourful cycle
by: Björklund, Andreas, et al.
Published: (2024)

A Faster Algorithm for Pigeonhole Equal Sums
by: Jin, Ce, et al.
Published: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
by: Chan, Timothy M., et al.
Published: (2023)

A parallel algorithm for the odd two-face shortest k-disjoint path problem
by: Chakraborty, Srijan, et al.
Published: (2025)

Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
by: Jin, Ce, et al.
Published: (2024)

Simple and Faster Algorithms for Knapsack
by: He, Qizheng, et al.
Published: (2023)

Faster optimal univariate microgaggregation
by: Stamm, Felix I., et al.
Published: (2024)

Faster Algorithms for Graph Monopolarity
by: Philip, Geevarghese, et al.
Published: (2024)

Faster Parameterized Vertex Multicut
by: Chu, Huairui, et al.
Published: (2026)

Faster Edge Coloring by Partition Sieving
by: Akmal, Shyan, et al.
Published: (2025)

Faster Global Minimum Cut with Predictions
by: Moseley, Benjamin, et al.
Published: (2025)

Faster Pseudo-Deterministic Minimum Cut
by: Kenneth-Mordoch, Yotam
Published: (2026)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster Approximate Linear Matroid Intersection
by: Terao, Tatsuya
Published: (2026)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

Graph parameters that are coarsely equivalent to path-length
by: Dragan, Feodor F., et al.
Published: (2025)

Approximate $2$-hop neighborhoods on incremental graphs: An efficient lazy approach
by: Becchetti, Luca, et al.
Published: (2025)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

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

Faster parameterized algorithm for 3-Hitting Set
by: Tsur, Dekel
Published: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

Faster Algorithm for Structured John Ellipsoid Computation
by: Cao, Yang, et al.
Published: (2022)