Cover Image

A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Li, Jason, Mowry, Connor
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Algorithm Engineering of SSSP With Negative Edge Weights
by: Cassis, Alejandro, et al.
Published: (2025)

Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
by: Li, Jason, et al.
Published: (2025)

Deterministic Padded Decompositions and Negative-Weight Shortest Paths
by: Li, Jason
Published: (2025)

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

Congestion-Approximators from the Bottom Up
by: Li, Jason, et al.
Published: (2024)

Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
by: Karczmarz, Adam, et al.
Published: (2025)

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

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

Uniform Sampling of Negative Edge Weights in Shortest Path Networks
by: Geis, Lukas, et al.
Published: (2024)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
by: Bernstein, Aaron, et al.
Published: (2022)

Beyond a Single Queue: Multi-Level-Multi-Queue as an Effective Design for SSSP problems on GPUs
by: Hu, Zhengding, et al.
Published: (2026)

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

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
by: Shakeri, Heman, et al.
Published: (2025)

Balancing Weights, Directed Sparsification, and Augmenting Paths
by: Li, Jason
Published: (2026)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

Concentration of Submodular Functions and Read-k Families Under Negative Dependence
by: Duppala, Sharmila, et al.
Published: (2023)

A Simple and Fast Algorithm for Fair Cuts
by: Li, Jason, et al.
Published: (2024)

Bounds on Longest Simple Cycles in Weighted Directed Graphs via Optimum Cycle Means
by: Dasdan, Ali
Published: (2025)

Competitive Transaction Admission in PCNs: Online Knapsack with Positive and Negative Items
by: Bienkowski, Marcin, et al.
Published: (2026)

Negative Momentum for Convex-Concave Optimization
by: Shugart, Henry, et al.
Published: (2026)

Finding Maximum Weight 2-Packing Sets on Arbitrary Graphs
by: Borowitz, Jannick, et al.
Published: (2025)

Local Sherman's Algorithm for Multi-commodity Flow
by: Li, Jason, et al.
Published: (2025)

Negative Stepsizes Make Gradient-Descent-Ascent Converge
by: Shugart, Henry, et al.
Published: (2025)

A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
by: Ghaffari, Mohsen, et al.
Published: (2024)

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, et al.
Published: (2024)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
by: Zhao, Jingyang, et al.
Published: (2023)

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

Non-iid hypothesis testing: from classical to quantum
by: De Palma, Giacomo, et al.
Published: (2025)

The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
by: Zhao, Jingyang, et al.
Published: (2024)

Weighted $k$-Server Admits an Exponentially Competitive Algorithm
by: Bijoy, Adithya, et al.
Published: (2025)

Settling Weighted Token Swapping up to Algorithmic Barriers
by: Wein, Nicole, et al.
Published: (2025)

Semi-Streaming Algorithms for Weighted $k$-Disjoint Matchings
by: Ferdous, S M, et al.
Published: (2023)

A Faster Algorithm for Maximum Weight Matching on Unrestricted Bipartite Graphs
by: Kwok, Shawxing
Published: (2025)

Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
by: Arkhipov, Pavel, et al.
Published: (2026)

Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
by: Bernstein, Aaron, et al.
Published: (2025)

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

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding
by: Gilani, Amin Shiraz, et al.
Published: (2024)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
by: Zheng, Da Wei, et al.
Published: (2023)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
by: Zhao, Jingyang, et al.
Published: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
by: Fan, Chenglin, et al.
Published: (2025)