# Talk:Path-based strong component algorithm

WikiProject Mathematics (Rated Start-class, Low-priority)
 .mw-parser-output .portalbox{float:right;border:solid #aaa 1px;padding:0}.mw-parser-output .portalbox.tleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalbox.tright{margin:0.5em 0 0.5em 1em}.mw-parser-output .portalbox>ul{display:table;box-sizing:border-box;padding:0.1em;max-width:175px;background:#f9f9f9;font-size:85%;line-height:110%;font-style:italic;font-weight:bold}.mw-parser-output .portalbox>ul>li{display:table-row}.mw-parser-output .portalbox>ul>li>span:first-child{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox>ul>li>span:last-child{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}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. Start This article has been rated as Start-Class on the project's quality scale. Low This article has been rated as Low-priority on the project's priority scale.

This algorithm was discovered by Cheriyan and Mehlhorn in 1996. So the algorithm should be called Cheriyan-Mehlhorn, or perhaps Cheriyan-Mehlhorn/Gabow ?

Path-based depth-first search for strong and biconnected components," Information Processing Letters 74, 2000, pp.107-114. Note added May 2006: Joseph Cheriyan and Kurt Mehlhorn published this algorithm several years before: "Algorithms for Dense Graphs and Networks on the Random Access Computer", Algorithmica 15, 1996, pp.521-549 postscript The final algorithms are the same, although they do not use the path-based approach for the high-level algorithm. Full version (15 pages) of IPL article Supplementary material on DFS.

85.216.120.110 06:22, 24 September 2007 (UTC)

Also Dijkstra presented this algorithm in Ch 25 of his 1976 book, A Discipline of Programming. A brief summary is on the webpage http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html Hngabow (talk) 23:05, 13 September 2011 (UTC)

a. Edsger Dijkstra presented this algorithm in his 1976 book on beautiful algorithms [D].

b. I think the best name for the algorithm is 'Dijkstra's strong component algorithm', because (i) Dijkstra appears to have discovered it; (ii) 'Dijkstra's algorithm' refers to his shortest path algorithm, in common parlance; (iii) most importantly, people use 'Tarjan's algorithm' to refer to his strong component algorithm. But eponyms are basically a bad idea. It would be better to call this the 'path-based strong component algorithm', and call Tarjan's the 'tree-based strong component algorithm', the motivation being that this algorithm views depth-first search as constructing a path, and Tarjan's algorithm views depth-first search as constructing a tree.

c. The article can mention the other published re-discoveries of the algorithm, in [CM] and [G]. Or maybe not - it would be best to be consistent with how other algorithms are treated in Wikipedia.

d. The article in its current form emphasizes data structures and other the low level details. It should start with the high level idea: The algorithm shrinks strongly connected sets as it discovers them. These sets form the vertices of a depth-first search path. The last vertex of the path is removed when it contains a complete strong component.

e. The path-based approach to depth-first search is discussed explicitly in [D]. Other applications of path-based depth-first search are discussed in [G2].

[CM] J. Cheriyan and K. Mehlhorn, Algorithms for dense graphs and networks on the random access computer, Algorithmica 15(1996), 521-549.

[D] E.W. Dijkstra, A Discipline of Programming, Prentice Hall, NJ, 1976, Ch.25. The web-page

reviews how the algorithm corresponds to the others, although this will be apparent to anyone reading Ch.25.

[G] H.N. Gabow, Path-based depth-first search for strong and biconnected components, Information Processing Letters 74(2000), 107-114.

[G2] H.N. Gabow, Searching (Ch 10.1), in J.L. Gross, J. Yellen, Discrete Math. and its Applications: Handbook of Graph Theory, 25, CRC Press, (2003), 953-984.

Hngabow (talk) 15:29, 30 January 2012 (UTC)