This is an old revision of this page, as edited by RobinK(talk | contribs) at 20:52, 2 January 2010(Rating article for WikiProject Mathematics. Quality: Start / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.Revision as of 20:52, 2 January 2010 by RobinK(talk | contribs)(Rating article for WikiProject Mathematics. Quality: Start / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page.)
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the |auto= parameter.
Confusion
"Aho, Hopcroft and Ullman credit it to an unpublished paper from 1978 by S. Rao Kosaraju" -- but Aho, Hopcroft and Ullman, as referenced in the article, was (apparently) published in 1974... — Matt Crypto09:24, 16 February 2009 (UTC)[reply]
As far as I know, Kosaraju's algorithm first appeared in print in M. Sharir, "A strong-connectivity algorithm and its application in data flow analysis", Computer and Mathematics with Applications, vol 7 nr 1, pp. 67--72, 1981. Snudehygel (talk) 22:23, 8 May 2009 (UTC)[reply]
The source of confusion appears to be the following statement in Cormen et al. algoritms book (I have the 1990 edition of CLRS at hand). The chapter notes on "Elementary Graph Algorithms" says:
"The algorithm [...] is adapted from Aho, Hopcroft and Ullman [5], who credit it to S.R. Kosaraju and M. Sharir."
In the references section of CLRS, we find the following entry:
[4] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley 1974.
[5] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. Data Structures and Algorithms. Addison-Wesley, 1983.
I would suggest that someone goes to a library and checks what is actually stated in reference [5]. (Sigh. I suppose that errors which cannot be verified with the aid of an internet search engine will actually never be fixed on wikipedia.) 134.176.28.77 (talk) 13:08, 10 August 2009 (UTC)[reply]
