Content deleted Content added
m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Merge {{VA}} into {{WPBS}}. Create {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Remove 2 same ratings as {{WPBS}} in {{Maths rating}}, {{WikiProject Computer science}}. |
m Reverted edit by 137.132.215.131 (talk) to last version by JustinBlank |
||
| (5 intermediate revisions by 3 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|vital=yes|1=
{{WikiProject Mathematics|priority=Mid
{{WikiProject Computer science|importance=high}}
}}
Line 228 ⟶ 227:
Hello! This is a note to let the editors of this article know that [[:File:MAZE 30x20 Prim.ogv]] will be appearing as [[Wikipedia:picture of the day|picture of the day]] on June 12, 2015. You can view and edit the POTD blurb at [[Template:POTD/2015-06-12]]. If this article needs any attention or maintenance, it would be preferable if that could be done before its appearance on the [[Main Page]]. Thanks! — [[User:Crisco 1492|Chris Woodrich]] ([[User talk:Crisco 1492|talk]]) 23:50, 22 May 2015 (UTC)
{{POTD/2015-06-12}}
== Linear Time For Dense Graphs ==
The article currently claims "However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.[10]". The reference is to Tarjan, "Data Structures and Network Algorithms", page 77. While I am only now learning about Prim's algorithm, I do not believe this is accurate. The page states:
: The running time of this implementation is dominated by the heap operations, of which there are n — 1 deletemin operations, n — 1 insert operations, and at most m — n + 1 siftup operations. By the analysis of §3.2, the total running time is 0(n d logd n + m logd n).
I cannot find anything on that page that indicates that the algorithm is ever linear. [[User:JustinBlank|JustinBlank]] ([[User talk:JustinBlank|talk]]) 19:06, 27 October 2024 (UTC)
| |||