Dijkstra, Floyd and Warshall meet Kleene

DOI10.1007/s00165-012-0245-4zbMath1259.68243OpenAlexW2045246689MaRDI 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

algorithmsalgebrasemiringKleene algebrashortest-path

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Applications of universal algebra in computer science (08A70) Semirings (16Y60)

Related Items

Stone Relation Algebras ⋮ Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm ⋮ Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras ⋮ Hopscotch -- reaching the target hop by hop ⋮ Incremental evaluation of continuous preference queries ⋮ Verifying minimum spanning tree algorithms with Stone relation algebras ⋮ An algebraic framework for minimum spanning tree problems ⋮ 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