• Login
    View Item 
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    •   MINDS@UW Home
    • MINDS@UW Madison
    • College of Letters and Science, University of Wisconsin–Madison
    • Department of Computer Sciences, UW-Madison
    • CS Technical Reports
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    A Transitive Closure Algorithm

    Thumbnail
    File(s)
    TR33.pdf (2.589Mb)
    Date
    1968
    Author
    Purdom, Paul W.
    Publisher
    University of Wisconsin-Madison Department of Computer Sciences
    Metadata
    Show full item record
    Abstract
    An algorithm is given for computing the transitive closure of a directed graph in a time no greater than a1 N1 n + a2n2 for large n where a1 and a2 are constants depending on the computer used to execute the algorithm, n is the number of nodes in the graph and N1 is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probability p , the average time to compute the transitive closure is no greater than min {a1 pn3 + a2n2, 1/2a1n2p-2+a2n2} for large n . The algorithm will compute the transitive closure of an undirected graph in a time no greater than a2n2 for large n. The method uses about n2 + n bits and 5n words of storage (where each word can hold n + 2 values).
    Permanent Link
    http://digital.library.wisc.edu/1793/57514
    Citation
    TR33
    Part of
    • CS Technical Reports

    Contact Us | Send Feedback
     

     

    Browse

    All of MINDS@UWCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Contact Us | Send Feedback