Buchumschlag

Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Koo, Jaehyun
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LIS
von: Koo, Jaehyun
Veröffentlicht: (2024)

Improved Additive Approximation Algorithms for APSP
von: Jin, Ce, et al.
Veröffentlicht: (2025)

Parallel Batch-Dynamic Algorithms for Spanners, and Extensions
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Bootstrapping Dynamic APSP via Sparsification
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

Dynamic Graph Coloring: Sequential, Parallel, and Distributed
von: Ghaffari, Mohsen, et al.
Veröffentlicht: (2025)

A Simple Dynamic Spanner via APSP
von: Kyng, Rasmus, et al.
Veröffentlicht: (2024)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
von: Roditty, Liam, et al.
Veröffentlicht: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
von: Nogler, Jakob, et al.
Veröffentlicht: (2024)

Universe Reduction for APSP: Equivalence of Three Fine-Grained Hypotheses
von: Fischer, Nick
Veröffentlicht: (2026)

Obstacle-Free Path Planning for Autonomous Drones Using Floyd Algorithm
von: Yao, Edward
Veröffentlicht: (2024)

Hardness and Approximation Algorithms for Balanced Districting Problems
von: Dharangutte, Prathamesh, et al.
Veröffentlicht: (2025)

New Algorithms and Hardness Results for Connected Clustering
von: Eube, Jan, et al.
Veröffentlicht: (2025)

Message Optimality and Message-Time Trade-offs for APSP and Beyond
von: Dufoulon, Fabien, et al.
Veröffentlicht: (2025)

On the Complexity of Knapsack under Explorable Uncertainty: Hardness and Algorithms
von: Schlöter, Jens
Veröffentlicht: (2025)

Algorithms and Hardness Results for the $(k,\ell)$-Cover Problem
von: Madani, Amirali, et al.
Veröffentlicht: (2025)

Automating the Search for Small Hard Examples to Approximation Algorithms
von: Sharma, Eklavya
Veröffentlicht: (2025)

Sparse Navigable Graphs for Nearest Neighbor Search: Algorithms and Hardness
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Almost Tight Approximation Hardness and Online Algorithms for Resource Scheduling
von: Das, Rathish, et al.
Veröffentlicht: (2025)

On the 2D Demand Bin Packing Problem: Hardness and Approximation Algorithms
von: Albers, Susanne, et al.
Veröffentlicht: (2025)

Improved Approximation Algorithms and Hardness Results for Shortest Common Superstring with Reverse Complements
von: Yamano, Ryosuke, et al.
Veröffentlicht: (2026)

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

Gabow's Cardinality Matching Algorithm in General Graphs: Implementation and Experiments
von: Ansaripour, Matin, et al.
Veröffentlicht: (2024)

Algorithms and Hardness for Estimating Statistical Similarity
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

Destroying Densest Subgraphs is Hard
von: Bazgan, Cristina, et al.
Veröffentlicht: (2024)

Hardness and Approximation for Coloring Digraphs
von: Chalermsook, Parinya, et al.
Veröffentlicht: (2026)

Implementation and Brief Experimental Analysis of the Duan et al. (2025) Algorithm for Single-Source Shortest Paths
von: Castro, Lucas, et al.
Veröffentlicht: (2025)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2026)

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
von: Gadekar, Ameet, et al.
Veröffentlicht: (2025)

Hardness Amplification for Dynamic Binary Search Trees
von: Jiang, Shunhua, et al.
Veröffentlicht: (2024)

Hitting Meets Packing: How Hard Can it Be?
von: Focke, Jacob, et al.
Veröffentlicht: (2024)

Approximations and Hardness of Packing Partially Ordered Items
von: Doron-Arad, Ilan, et al.
Veröffentlicht: (2024)

Hardness and Tight Approximations of Demand Strip Packing
von: Jansen, Klaus, et al.
Veröffentlicht: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
von: Carlson, Charlie, et al.
Veröffentlicht: (2025)

Hardness of Dynamic Tree Edit Distance and Friends
von: Hu, Bingbing, et al.
Veröffentlicht: (2025)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
von: Antony, Dhanyamol, et al.
Veröffentlicht: (2023)

Comparing the Hardness of Online Minimization and Maximization Problems with Predictions
von: Berg, Magnus
Veröffentlicht: (2024)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2024)

When is String Reconstruction using de Bruijn Graphs Hard?
von: Bals, Ben, et al.
Veröffentlicht: (2025)