DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2024.19

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

Authors: Jaehyun Koo

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract

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.

Cite as

Jaehyun Koo. Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 19:1-19:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{koo:LIPIcs.FUN.2024.19,
  author =	{Koo, Jaehyun},
  title =	{{Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{19:1--19:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.19},
  URN =		{urn:nbn:de:0030-drops-199270},
  doi =		{10.4230/LIPIcs.FUN.2024.19},
  annote =	{Keywords: fine-grained complexity, recreational algorithms}
}

Search Results

Documents authored by Koo, Jaehyun

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

Abstract

Cite as

Thanks for your feedback!

Could not send message