@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},
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.},
}