Dijkstra, Floyd and Warshall meet Kleene

DOI10.1007/S00165-012-0245-4MaRDI QIDQ1941863zbMATH OpenOpenAlexFDO

Authors 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) Semirings (16Y60) Applications of universal algebra in computer science (08A70)

Recommendations

• Calculating path algorithms
• scientific article; zbMATH DE number 177548
• scientific article; zbMATH DE number 512947
• A walk over the shortest path: Dijkstra's algorithm viewed as fixed-point computation.
• scientific article; zbMATH DE number 3937196

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 176744 (Why is no real title available?)
• scientific article; zbMATH DE number 177548 (Why is no real title available?)
• scientific article; zbMATH DE number 1086671 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 3366846 (Why is no real title available?)
• scientific article; zbMATH DE number 3073037 (Why is no real title available?)
• A Theorem on Boolean Matrices
• A Unified Approach to Path Problems
• A completeness theorem for Kleene algebras and the algebra of regular events
• A note on two problems in connexion with graphs
• An Algebra for Network Routing Problems
• Automated Reasoning in Kleene Algebra
• Calculating path algorithms
• Graphs and algorithms
• Graphs, dioids and semirings. New models and algorithms.
• On a routing problem
• On the shortest route through a network
• Regular Algebra Applied to Path-finding Problems

Cited in

(12)

• An algebraic framework for minimum spanning tree problems
• Incremental evaluation of continuous preference queries
• Hopscotch -- reaching the target hop by hop
• Relation-algebraic verification of disjoint-set forests
• The Formal System of Dijkstra and Scholten
• Hierarchical multiobjective shortest path problems
• Kleene, Rabin, and Scott Are Available
• Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras
• Stone relation algebras
• Abstract interpretation of graphs
• Verifying minimum spanning tree algorithms with Stone relation algebras
• Relation-algebraic verification of Prim's minimum spanning tree algorithm

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Dijkstra, Floyd and Warshall meet Kleene

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