Cover Image

Bellman-Ford in Almost-Linear Time for Dense Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, George Z., Li, Jason, Zhang, Junkai
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

Deterministic Mincut in Almost-Linear Time
by: Li, Jason
Published: (2021)

Network Unreliability in Almost-Linear Time
by: Cen, Ruoxu, et al.
Published: (2025)

Breaking the Bellman-Ford Shortest-Path Bound
by: Elmasry, Amr
Published: (2024)

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

Non-adaptive Bellman-Ford: Yen's improvement is optimal
by: Hu, Jialu, et al.
Published: (2024)

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

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, 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)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
by: Henzinger, Monika, et al.
Published: (2024)

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

Separator Theorem for Minor-Free Graphs in Linear Time
by: Bonnet, Édouard, et al.
Published: (2025)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
by: Yoshida, Yuichi
Published: (2026)

Fast Algorithms for Graph Arboricity and Related Problems
by: Cen, Ruoxu, et al.
Published: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
by: Rao, Satish
Published: (2025)

Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
by: Jiang, Shunhua, et al.
Published: (2025)

Improved Directed Expander Decompositions
by: Fleischmann, Henry, et al.
Published: (2025)

Faster Weak Expander Decompositions and Approximate Max Flow
by: Fleischmann, Henry, et al.
Published: (2025)

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

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

Almost Linear Size Edit Distance Sketch
by: Koucký, Michal, et al.
Published: (2024)

Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method
by: Liu, Yang P.
Published: (2025)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Paths and Intersections: Exact Emulators for Planar Graphs
by: Li, George Z., et al.
Published: (2025)

JFR: An Efficient Jump Frontier Relaxation Strategy for Bellman-Ford
by: Wang, Xin, et al.
Published: (2025)

Beating Bellman's Algorithm for Subset Sum
by: Bringmann, Karl, et al.
Published: (2024)

Local Search for Clustering in Almost-linear Time
by: Jiang, Shaofeng H. -C., et al.
Published: (2025)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
by: Hu, Yang, et al.
Published: (2024)

Parameterized Complexity of Dominating Set Variants in Almost Cluster and Split Graphs
by: Goyal, Dishant, et al.
Published: (2024)

Linear-Time Multilevel Graph Partitioning via Edge Sparsification
by: Gottesbüren, Lars, et al.
Published: (2025)

Almost-Optimal Sublinear Additive Spanners
by: Tan, Zihan, et al.
Published: (2023)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

Colorful Priority $k$-Supplier
by: Chekuri, Chandra, et al.
Published: (2024)

Hypergraph Unreliability in Quasi-Polynomial Time
by: Cen, Ruoxu, et al.
Published: (2024)

Minimizing Reachability Times on Temporal Graphs via Shifting Labels
by: Deligkas, Argyrios, et al.
Published: (2021)

A Practical Linear Time Algorithm for Optimal Tree Decomposition of Halin Graphs
by: Alejandro-Soto, J. A., et al.
Published: (2025)

Directed and Undirected Vertex Connectivity Problems are Equivalent for Dense Graphs
by: Fischer, Olivier, et al.
Published: (2025)

Approximating Partition in Near-Linear Time
by: Chen, Lin, et al.
Published: (2024)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)