Dijkstra, Floyd and Warshall meet Kleene

DOI10.1007/S00165-012-0245-4zbMATH Open1259.68243OpenAlexW2045246689MaRDI QIDQ1941863FDOQ1941863

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

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

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)

Cites Work

• A note on two problems in connexion with graphs
• On a routing problem
• A Theorem on Boolean Matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs, dioids and semirings. New models and algorithms.
• An Algebra for Network Routing Problems
• Title not available (Why is that?)
• Calculating path algorithms
• A completeness theorem for Kleene algebras and the algebra of regular events
• Automated Reasoning in Kleene Algebra
• Title not available (Why is that?)
• On the shortest route through a network
• Regular Algebra Applied to Path-finding Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Graphs and algorithms
• A Unified Approach to Path Problems

Cited In (12)

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

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)