## Journal article

Title:

Algorithms for transitive closure

Authors:

Alena Koubková, Václav Koubek

Publication:

Information Processing Letters
81
(6)

Year:

2002

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