Autor:	Shokry, Ahmed, Elmasry, Amr, Khalafallah, Ayman, Aly, Amr
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	In this paper we propose a linear-time certifying algorithm for the single-source shortest-path problem capable of verifying graphs with positive, negative, and zero arc weights. Previously proposed linear-time approaches only work for graphs with positive arc weights.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2412.06121 Zobrazit plný text záznamu View this record from Arxiv