✦ LIBER ✦

An efficient transitive closure algorithm for cyclic digraphs

✍ Scribed by Esko Nuutila

Book ID: 107766238
Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 730 KB
Volume: 52
Category: Article
ISSN: 0020-0190
DOI: 10.1016/0020-0190(94)90128-7

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

An improved algorithm for transitive clo

An improved algorithm for transitive closure on acyclic digraphs

✍ Klaus Simon 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 910 KB

An efficient parallel algorithm for the

An efficient parallel algorithm for the transitive closure of a graph

✍ P. Fraisse 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 377 KB

An improved transitive closure algorithm

✍ L. Schmitz 📂 Article 📅 1983 🏛 Springer Vienna 🌐 English ⚖ 498 KB

Algorithmus 26 An algorithm for finding

Algorithmus 26 An algorithm for finding the transitive closure of a digraph

✍ J. Dzikiewicz 📂 Article 📅 1975 🏛 Springer Vienna 🌐 English ⚖ 194 KB

An Algorithm for Transitive Closure with

An Algorithm for Transitive Closure with Linear Expected Time

✍ Schnorr, C. P. 📂 Article 📅 1978 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 752 KB

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