Relation-algebraic derivation of spanning tree algorithms

DOI10.1007/BFB0054283MaRDI QIDQ4213376zbMATH OpenFDO

Authors Rudolf Berghammer, Burghard von Karger, Andreas Wolf

Publication date 9 December 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0054283

zbMATH Keywords

graph algorithmsrelational methodsspanning trees program development

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15) Graph algorithms (graph-theoretic aspects) (05C85) General topics in the theory of software (68N01) Graph theory (including graph drawing) in computer science (68R10)

Review text

Examples are given of modern relation-based development of a diversity of spanning-tree algorithms. The exposition is component-free as long as possible. A full and annotated proof of correctness is given along the development. Concepts such as bridges and cycles in a graph, incidence structures, etc. are given in relational form. It is intended to demonstrate the higher level of rigorousness of relational program development. An immediate realisation is given showing how the prototypes obtained work on the RelView-System. For the entire collection see [Zbl 0891.00027].

Recommendations

• Verifying minimum spanning tree algorithms with Stone relation algebras
• scientific article; zbMATH DE number 2013597
• Relation-algebraic verification of Prim's minimum spanning tree algorithm
• Algorithms from relational specifications

Cited in

(12)

• An algebraic framework for minimum spanning tree problems
• Combining relational calculus and the Dijkstra-Gries method for deriving relational programs
• Verifying minimum spanning tree algorithms with Stone relation algebras
• Relation-algebraic verification of Borůvka's minimum spanning tree algorithm
• Relation-algebraic verification of Prim's minimum spanning tree algorithm
• scientific article; zbMATH DE number 3908451 (Why is no real title available?)
• Algorithms from relational specifications
• scientific article; zbMATH DE number 2013597 (Why is no real title available?)
• Verifying the Correctness of Disjoint-Set Forests with Kleene Relation Algebras
• Stone relation algebras
• Relation-algebraic verification of disjoint-set forests
• Relational Disjoint-Set Forests

Describes a project that uses

Uses Software

• RelView

This page was built for publication: Relation-algebraic derivation of spanning tree algorithms

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