Warshall's algorithm-survey and applications

DOI10.33039/AMI.2021.08.001MaRDI QIDQ5065315zbMATH OpenOpenAlexFDO

Authors Zoltán Kása

Publication date 18 March 2022

Published in Annales Mathematicae et Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.00276

zbMATH Keywords

finite automataFloyd-Warshall algorithmpaths in graphsscattered subword complexityWarshall's algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05)

Abstract: The survey presents the well-known Warshall's algorithm, a generalization and some interesting applications of this.

Recommendations

• Abstract derivation of transitive closure algorithms
• A functional, successor list based version of Warshall's algorithm with applications
• An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs
• scientific article; zbMATH DE number 88951
• Calculating path algorithms

Cited in

(2)

• Abstract derivation of transitive closure algorithms
• A functional, successor list based version of Warshall's algorithm with applications

This page was built for publication: Warshall's algorithm-survey and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065315)