Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917685323890688 |
|---|---|
| author | Koo, Jaehyun |
| author_facet | Koo, Jaehyun |
| contents | The celebrated Floyd-Warshall algorithm efficiently computes the all-pairs shortest path, and its simplicity made it a staple in computer science classes. Frequently, students discover a variant of this Floyd-Warshall algorithm by mixing up the loop order, ending up with the incorrect APSP matrix. This paper considers a computational problem of computing this incorrect APSP matrix. We will propose efficient algorithms for this problem and prove that this incorrect variant is APSP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_08173 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall Koo, Jaehyun Data Structures and Algorithms The celebrated Floyd-Warshall algorithm efficiently computes the all-pairs shortest path, and its simplicity made it a staple in computer science classes. Frequently, students discover a variant of this Floyd-Warshall algorithm by mixing up the loop order, ending up with the incorrect APSP matrix. This paper considers a computational problem of computing this incorrect APSP matrix. We will propose efficient algorithms for this problem and prove that this incorrect variant is APSP-complete. |
| title | Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.08173 |