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 Ruud Koot (talk | contribs) at 13:24, 22 February 2011 (moved Talk:Gabow's algorithm to Talk:Cheriyan–Mehlhorn/Gabow algorithm: original title is ambiguous). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
WikiProject iconMathematics Stub‑class Low‑priority
WikiProject iconThis 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
StubThis article has been rated as Stub-class on Wikipedia's content assessment scale.
LowThis 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 ?

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]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Path-based_strong_component_algorithm&oldid=415315637"