Jump to content

Talk:Path-based strong component algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by 85.216.120.110 (talk) at 06:21, 24 September 2007 (Created page with '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 a...'). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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.