Talk:Path-based strong component algorithm - Revision history

Cewbot: Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Maths rating}}. Remove 1 deprecated parameter: field.

2024-02-07T09:30:10Z

Maintain {{WPBS}} and vital articles: 1 WikiProject template. Create {{WPBS}}. Keep majority rating "Start" in {{WPBS}}. Remove 1 same rating as {{WPBS}} in {{Maths rating}}. Remove 1 deprecated parameter: field.

← Previous revision		Revision as of 09:30, 7 February 2024
Line 1:		Line 1:
	{{~~maths~~ ~~rating~~\|class=Start\|~~priority=Low\|field=discrete}}~~		{{WikiProject banner shell\|class=Start\|
			{{WikiProject Mathematics\|priority=Low}}
			}}
	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

A smart kitten: notify target page of rfd for Gabow's algorithm

2023-12-12T10:53:22Z

notify target page of rfd for Gabow's algorithm

← Previous revision		Revision as of 10:53, 12 December 2023
Line 57:		Line 57:

	[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 15:29, 30 January 2012 (UTC)		[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 15:29, 30 January 2012 (UTC)

			== "[[:Gabow's algorithm]]" listed at [[Wikipedia:Redirects for discussion\|Redirects for discussion]] ==
			[[File:Information.svg\|30px]]
			The redirect <span class="plainlinks">[//en.wikipedia.org/w/index.php?title=Gabow%27s_algorithm&redirect=no Gabow's algorithm]</span> has been listed at [[Wikipedia:Redirects for discussion\|redirects for discussion]] to determine whether its use and function meets the [[Wikipedia:Redirect\|redirect guidelines]]. Readers of this page are welcome to comment on this redirect at '''{{slink\|Wikipedia:Redirects for discussion/Log/2023 December 12#Gabow's algorithm}}''' until a consensus is reached. <!-- Template:RFDNote --> Best, <sup style="letter-spacing:-.1em;color:#737373;font-family:monospace">user:</sup>[[User:A smart kitten\|<span style="color:#ff8352">'''A smart kitten'''</span>]][[User talk:A smart kitten\|<sub style="color:#b842b8;font-family:monospace">''meow''</sub>]] 10:53, 12 December 2023 (UTC)

David Eppstein: this is start class, not a stub

2013-11-07T19:05:21Z

this is start class, not a stub

← Previous revision		Revision as of 19:05, 7 November 2013
Line 1:		Line 1:
	{{maths rating\|class=~~Stub~~\|priority=Low\|field=discrete}}		{{maths rating\|class=Start\|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

David Eppstein: David Eppstein moved page Talk:Cheriyan–Mehlhorn/Gabow algorithm to Talk:Path-based strong component algorithm: Per talk

2012-04-24T22:59:27Z

David Eppstein moved page Talk:Cheriyan–Mehlhorn/Gabow algorithm to Talk:Path-based strong component algorithm: Per talk

← Previous revision	Revision as of 22:59, 24 April 2012
(No difference)

Hngabow at 15:29, 30 January 2012

2012-01-30T15:29:59Z

← Previous revision		Revision as of 15:29, 30 January 2012
Line 15:		Line 15:
	A brief summary is on the webpage http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html		A brief summary is on the webpage http://www.cs.colorado.edu/~hal/Papers/DFS/pbDFShistory.html
	[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 23:05, 13 September 2011 (UTC)		[[User:Hngabow\|Hngabow]] ([[User talk: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

			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.

			[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 15:29, 30 January 2012 (UTC)

Hngabow at 23:05, 13 September 2011

2011-09-13T23:05:40Z

← Previous revision		Revision as of 23:05, 13 September 2011
Line 11:		Line 11:

	[[User:85.216.120.110\|85.216.120.110]] 06:22, 24 September 2007 (UTC)		[[User:85.216.120.110\|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
			[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 23:05, 13 September 2011 (UTC)

Ruud Koot: moved Talk:Gabow's algorithm to Talk:Cheriyan–Mehlhorn/Gabow algorithm: original title is ambiguous

2011-02-22T13:24:18Z

moved Talk:Gabow's algorithm to Talk:Cheriyan–Mehlhorn/Gabow algorithm: original title is ambiguous

← Previous revision	Revision as of 13:24, 22 February 2011
(No difference)

RobinK: Rating article for WikiProject Mathematics. Quality: Stub / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page.

2010-01-02T20:49:07Z

Rating article for WikiProject Mathematics. Quality: Stub / Priority: Low / Field: discrete (script assisted). Please report any errors on my talk page.

← Previous revision		Revision as of 20:49, 2 January 2010
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

85.216.120.110 at 06:22, 24 September 2007

2007-09-24T06:22:58Z

← Previous revision		Revision as of 06:22, 24 September 2007
Line 8:		Line 8:
	Full version (15 pages) of IPL article		Full version (15 pages) of IPL article
	Supplementary material on DFS.		Supplementary material on DFS.

			[[User:85.216.120.110\|85.216.120.110]] 06:22, 24 September 2007 (UTC)

85.216.120.110: ←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...'

2007-09-24T06:21:42Z

←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...'

New page

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.

← Previous revision		Revision as of 10:53, 12 December 2023
Line 57:		Line 57:

	[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 15:29, 30 January 2012 (UTC)		[[User:Hngabow\|Hngabow]] ([[User talk:Hngabow\|talk]]) 15:29, 30 January 2012 (UTC)

			== "[[:Gabow's algorithm]]" listed at [[Wikipedia:Redirects for discussion\|Redirects for discussion]] ==
			[[File:Information.svg\|30px]]
			The redirect <span class="plainlinks">[//en.wikipedia.org/w/index.php?title=Gabow%27s_algorithm&redirect=no Gabow's algorithm]</span> has been listed at [[Wikipedia:Redirects for discussion\|redirects for discussion]] to determine whether its use and function meets the [[Wikipedia:Redirect\|redirect guidelines]]. Readers of this page are welcome to comment on this redirect at '''{{slink\|Wikipedia:Redirects for discussion/Log/2023 December 12#Gabow's algorithm}}''' until a consensus is reached. <!-- Template:RFDNote --> Best, <sup style="letter-spacing:-.1em;color:#737373;font-family:monospace">user:</sup>[[User:A smart kitten\|<span style="color:#ff8352">'''A smart kitten'''</span>]][[User talk:A smart kitten\|<sub style="color:#b842b8;font-family:monospace">''meow''</sub>]] 10:53, 12 December 2023 (UTC)