𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithms for transitive closure

✍ Scribed by A. Koubková; V. Koubek

Book ID
104136656
Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
105 KB
Volume
81
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

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 present a new algorithm constructing the transitive closure of an acyclic graph.

📜 SIMILAR VOLUMES

Abstract derivation of transitive closur
Abstract derivation of transitive closure algorithms
✍ L.M.G. Feijs; R.C. van Ommering 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 529 KB

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 lo