JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Time Required to Detect Cycles and Connectivity in Directed Graphs

Author
Holt, Richard C.; Reingold, E.M.
Abstract
It is shown that when a directed graph is represented as a binary connection matrix, the problem of finding the shortest path between two nodes of a directed graph, and the problem of determining whether the directed graph has a cycle require at least $O(n^{2})$ operations. Thus the presently known best algorithms are optimal to within a multiplicative constant.
Date Issued
1970-06Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR70-63
Type
technical report