{"id":"arxiv:2412.06121","kind":"article","title":"Verifying Shortest Paths in Linear Time","authors":["Ahmed Shokry","Amr Elmasry","Ayman Khalafallah","Amr Aly"],"author_count":4,"year":2024,"published":"2024-12-09","venue":"International Japan-Africa Conference on Electronics, Communications, and Computations (JAC-ECC)","cited_by":0,"doi":"10.1109/jac-ecc64419.2024.11061218","arxiv_id":"2412.06121","nct_id":null,"source_url":"https://arxiv.org/abs/2412.06121","archive_url":"https://space-kitty.com/papers/arxiv:2412.06121","updated":"2024-12-09","pmid":null,"pmcid":null,"openalex_id":"W4412130541","pdf_url":"https://arxiv.org/pdf/2412.06121","abstract":"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.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":null,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[{"slug":"algorithms-complexity","name":"Algorithms & Complexity Breakthroughs","domain_slug":"math-cs"}],"cited_in_dossiers":[]}