Talk:Path-based strong component algorithm

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

Here is an excerpts from Gabow's home page:

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)[reply]

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)[reply]

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

http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html

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)[reply]

"Gabow's algorithm" listed at Redirects for discussion

The redirect Gabow's algorithm has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2023 December 12 § Gabow's algorithm until a consensus is reached. Best, ^user:A smart kitten_meow 10:53, 12 December 2023 (UTC)[reply]