Talk:Path-based strong component algorithm: Difference between revisions
Content deleted Content added
No edit summary |
Rating article for WikiProject Mathematics. Quality: Stub / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page. |
||
| Line 1: | Line 1: | ||
{{maths rating|class=Stub|priority=Low|field=discrete}} |
|||
This algorithm was discovered by Cheriyan and Mehlhorn in 1996. |
This algorithm was discovered by Cheriyan and Mehlhorn in 1996. |
||
So the algorithm should be called Cheriyan-Mehlhorn, or |
So the algorithm should be called Cheriyan-Mehlhorn, or |
||
Revision as of 20:49, 2 January 2010
 | Mathematics Stub‑class Low‑priority | |||||||||
| ||||||||||
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.