Algorithms for transitive closure

Journal article

Title:

Authors:

A. Koubková, V. Koubek

Publication:

Information Processing Letters 81 (6)

DOI:

10.1016/S0020-0190(01)00245-9

Year:

2002

Link:

http://www.sciencedirect.com/science/article/pii/S0020019001002459

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