Dijkstra, Floyd and Warshall meet Kleene

DOI10.1007/s00165-012-0245-4zbMath1259.68243MaRDI QIDQ1941863

Peter Höfner, Bernhard Möller

Publication date: 22 March 2013

Published in: Formal Aspects of Computing (Search for Journal in Brave)

Full work available at URL: https://opus.bibliothek.uni-augsburg.de/opus4/frontdoor/index/index/docId/58760

zbMATH Keywords

algorithms; algebra; semiring; Kleene algebra; shortest-path

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

08A70: Applications of universal algebra in computer science

16Y60: Semirings

Related Items

Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras, Stone Relation Algebras, Hopscotch -- reaching the target hop by hop, An algebraic framework for minimum spanning tree problems, Verifying minimum spanning tree algorithms with Stone relation algebras, Incremental evaluation of continuous preference queries, Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm, Hierarchical Multiobjective Shortest Path Problems

Uses Software

• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A completeness theorem for Kleene algebras and the algebra of regular events
• Calculating path algorithms
• Graphs, dioids and semirings. New models and algorithms.
• On the Shortest Route Through a Network
• On a routing problem
• Automated Reasoning in Kleene Algebra
• A Unified Approach to Path Problems
• Regular Algebra Applied to Path-finding Problems
• An Algebra for Network Routing Problems
• A Theorem on Boolean Matrices