๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Abstract derivation of transitive closure algorithms

โœ Scribed by L.M.G. Feijs; R.C. van Ommering

Book ID
104137448
Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
529 KB
Volume
63
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

We state Warshall's algorithm in an abstract form and prove its correctness, while postponing the choices of representation. This is achieved by the use of relations and algebraic operations on relations, avoiding the use of vectors, matrix elements and indices. By choosing specific forms for the loop-body we derive Warshall's algorithm, the grid algorithm and generalisations of the latter. The derivation illustrates the point that nontrivial algorithms need not have difficult derivations, provided the right abstractions are chosen and provided the right notation is employed. @

๐Ÿ“œ SIMILAR VOLUMES

Algorithms for transitive closure
Algorithms for transitive closure
โœ A. Koubkovรก; V. Koubek ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 105 KB

Let ฯƒ (n) denote the number of all strongly connected graphs on the n-element set. We prove that ฯƒ (n) ). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n 2 ), under the assumption of uniform distribution of input graphs. Furthermore, we

A transitive closure algorithm
A transitive closure algorithm
โœ Paul Purdom ๐Ÿ“‚ Article ๐Ÿ“… 1970 ๐Ÿ› Springer Netherlands ๐ŸŒ English โš– 997 KB