Loading...
Please wait, while we are loading the content...
Similar Documents
An Improved Algorithm for Finding the Strongly Connected Components of a Directed Graph
| Content Provider | Semantic Scholar |
|---|---|
| Author | Pearce, David J. Pearce, David. |
| Copyright Year | 2005 |
| Abstract | For a directed graph D = (V,E), aStrongly Connected Component (SCC) is a maximal induced subgraph S = (VS , ES) where, for everyx, y ∈ VS , there is a path fromx to y (and vice-versa). Tarjan presented a now well-established algorithm for computing the strongl y connected components of a digraph in time Θ(v+e) [8]. In the worst case, this needs v(2 + 5w) bits of storage, where w is the machine’s word size. Nuutila and Soisalon-Soininen reduced this to v(1 + 4w) [6]. In this paper, we present for the first time an algorithm requiring only3vw bits in the worst case. Tarjan’s algorithm has found numerous uses in the literatur e, often as a subcomponent of larger algorithms, such as those for transitive closure[5], compiler optimisation[3] andprogram analysis[1, 7] to name but a few. Of particular relevance is its use in model c h cking, where the algorithm’s storage requirements are a critical factor limiting the number of st ates which can be explored [4]. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://homepages.ecs.vuw.ac.nz/~djp/files/P05.pdf |
| Alternate Webpage(s) | http://homepages.mcs.vuw.ac.nz/~djp/files/P05.pdf |
| Alternate Webpage(s) | http://www.mcs.vuw.ac.nz/~djp/files/P05.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
