Cover Image

Algorithm Engineering of SSSP With Negative Edge Weights

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cassis, Alejandro, Karrenbauer, Andreas, Nusser, André, Rinaldi, Paolo Luigi
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

A Bottom-Up Algorithm for Negative-Weight SSSP with Integrated Negative Cycle Finding
by: Li, Jason, et al.
Published: (2024)

Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
by: Ghosal, Angikar, et al.
Published: (2025)

Improving Order with Queues
by: Karrenbauer, Andreas, et al.
Published: (2022)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
by: Saller, Sophia, et al.
Published: (2023)

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

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

Engineering Edge Orientation Algorithms
by: Reinstädtler, H., et al.
Published: (2024)

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

Engineering Weighted Connectivity Augmentation Algorithms
by: Faraj, Marcelo Fonseca, 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)

Shortcutting for Negative-Weight Shortest Path
by: Li, George Z., 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)

Graph Exploration with Edge Weight Estimates
by: Gehnen, Matthias, et al.
Published: (2025)

Weighted Partition Vertex and Edge Cover
by: Dabas, Rajni, et al.
Published: (2025)

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

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

Broadcasting in Heterogeneous Tree Networks with Edge Weight Uncertainty
by: Tsou, Cheng-Hsiao, et al.
Published: (2024)

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

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Methodology of Algorithm Engineering
by: Mendling, Jan, et al.
Published: (2023)

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

Simple Algorithms for Fully Dynamic Edge Connectivity
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

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

Faster Vizing and Near-Vizing Edge Coloring Algorithms
by: Assadi, Sepehr
Published: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

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)

Dimensionality Reduction on Complex Vector Spaces for Euclidean Distance with Dynamic Weights
by: Moretti, Simone, et al.
Published: (2022)

Engineering Hypergraph $b$-Matching Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

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)

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

Optimizing Administrative Divisions: A Vertex $k$-Center Approach for Edge-Weighted Road Graphs
by: Daugulis, Peteris
Published: (2025)

Improved Learning via k-DTW: A Novel Dissimilarity Measure for Curves
by: Krivošija, Amer, et al.
Published: (2025)

Engineering Algorithms for Dynamic Greedy Set Cover
by: Uzrad, Amitai
Published: (2026)

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

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

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