Journal article

Title:
Algorithms for transitive closure
Authors:
Alena Koubková, Václav Koubek
Publication:
Information Processing Letters 81 (6)
DOI:
Year:
2002
Link:

Abstract:
Let σ′(n) denote the number of all strongly connected graphs on the n-element set. We prove that σ′(n)⩾2n2·(1−n(n−1)/2n−1). Hence the algorithm computing a transitive closure by a reduction to acyclic graphs has the expected time O(n2), under the assumption of uniform distribution of input graphs. Furthermore, we present a new algorithm constructing the transitive closure of an acyclic graph.

BibTeX:
@article{koubkova_algorithms_2002,
    title = {{Algorithms for transitive closure}},
    author = {Koubková, Alena and Koubek, Václav},
    year = {2002},
    journal = {{Information Processing Letters}},
    number = {6},
    doi = {10.1016/S0020-0190(01)00245-9},
    issn = {0020-0190},
    pages = {289--296},
    url = {http://www.sciencedirect.com/science/article/pii/S0020019001002459},
    volume = {81},
}