Talk:Tarjan's strongly connected components algorithm: Difference between revisions

Revision as of 13:47, 9 December 2015

Revision as of 13:58, 9 December 2015

Line 242:

: Well that would bring the pseudocode back to Tarjan's original. MattGiuca considered this above under Status of the algorithm and reasoned that v, just numbered, would have to be greater than any existing number. But while numbering v happens before looping over successors, it does seems that a recursive call to strongconnect on one successor of v could number a later successor of v. I'm inclined to agree that this looks like a problem but a test case might show it clearly. Do you have an example of a graph that shows this failure? —[[User:Fifteen Minutes Of Fame|Fifteen Minutes Of Fame]] ([[User talk:Fifteen Minutes Of Fame|talk]]) 15:56, 28 March 2015 (UTC)

== Relation to Kosaraju's algorithm ==

Thinking about the matter a bit more, I find it highly unlikely that Tarjan's algorithm can be derived from [[Kosaraju's algorithm]]. Unless anyone can come up with a source for the claim

: Although proposed earlier, [Tarjan's algorithm] can be seen as an improved version of Kosaraju's algorithm

then it should be removed. [[Special:Contributions/130.243.94.123|130.243.94.123]] ([[User talk:130.243.94.123|talk]]) 13:58, 9 December 2015 (UTC)