A sensitive transitive closure algorithm

Several well-known algorithms have been introduced to solve the 2 closely related problems for a directed graph. These problems are the transitive closure problem and the reachability problem. A new algorithm is presented, superior to the prior algorithms in that these others are not sensitive to th...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1981-10, Vol.12 (5), p.255-258
Main Author: Ebert, Jürgen
Format: Article
Language:English
Subjects:
Algorithms
Computer science
depth-first search
Graph
Information processing
reachability
transitive closure
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Several well-known algorithms have been introduced to solve the 2 closely related problems for a directed graph. These problems are the transitive closure problem and the reachability problem. A new algorithm is presented, superior to the prior algorithms in that these others are not sensitive to the graph structure, requiring an execution time dependent only on the number of vertices of the given graph. The new algorithm computes the transitive closure and can be modified to determine the reflexivo-transitive closure. The algorithm uses depth-first search.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(81)90026-0