Talk:Borůvka's algorithm: Difference between revisions

Revision as of 15:10, 12 October 2010

Latest revision as of 23:37, 8 March 2024

(17 intermediate revisions by 11 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{maths rating|class=Start|priority=Low|field=discrete}}

{{WikiProject ComputingMathematics|class=Start|importancepriority=Low }}

{{WikiProject ComputerComputing science|importance=Low}}

{{WikiProject Computer science |importance=Mid}}

|class=Start

|importance=Mid

}}

----

== References for the other authors: ==

Line 13 ⟶ 12:

<small><span class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Rps|Rps]] ([[User talk:Rps|talk]] • [[Special:Contributions/Rps|contribs]]) 13:57, 12 October 2010 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->

:I found the references:

:[17] K. Florek, J. Łukaszewicz, H. Perkal, H. Steinhaus and S. Zubrzycki, Sur la liaison et la division des points d’un ensemble fini, Colloquium Mathematicum 2 (1951), pp. 282–285.

:[18] M. Sollin, Le trace de canalisation. In: C. Berge and A. Ghouilla-Houri, Editors, Programming, Games, and Transportation Networks, Wiley, New York (1965) (in French).

:Found in "The saga of minimum spanning trees" by Martin Mareš, available from [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B8JDG-4TVR2H2-1&_user=2459680&_origUdi=B6WH3-4D7JN2B-3W&_fmt=high&_coverDate=12%2F31%2F2008&_rdoc=1&_orig=article&_origin=article&_zone=related_art&_acct=C000057391&_version=1&_urlVersion=0&_userid=2459680&md5=5b7d453d6f8b83f1ce83a62c4ee023dd#bibl001 http://www.sciencedirect.com/] .

:Still lacks references to parallel implementations. I found the paper: "A parallel algorithm for constructing minimum spanning trees" by Jon Louis Bentley, Journal of Algorithms Volume 1, Issue 1, March 1980, Pages 51-59, but it seems to be about an alternative or improvement to the Sollin algorithm, not its parallel implementation.

[[User:Rps|Rps]] ([[User talk:Rps|talk]]) 15:10, 12 October 2010 (UTC)

::About parallel implementations I found this: "Among these[Prim's, Kruskal's, Sollin's] minimum spanning tree algorithms, the Sollin algorithm is the most suitable candidate for parallel processing.", Advances in computers, Volume 26 By Marshall C. Yovits, page 113, [http://books.google.com/books?id=fAtH4_VEgDMC&pg=PA113&dq=sollin&hl=en&ei=6Wy0TIXVDoGXOv3j2JYK&sa=X&oi=book_result&ct=result&resnum=7&ved=0CEAQ6AEwBg http://books.google.com/] [[User:Rps|Rps]] ([[User talk:Rps|talk]]) 16:25, 12 October 2010 (UTC)

----

Line 127 ⟶ 128:

Some of this can definitely be used to expand the article. However, there are some consistent problems in tone that I think prevent it from being immediately useful. I've moved the contribution here to keep it visible, but I will remove it from the article. [[User:Michael Slone|Michael Slone]] ([[User talk:Michael Slone|talk]]) 02:35, 15 January 2009 (UTC)

== Why should we limit the input to graphs with distinct edge weights? ==

Observe that none of the steps in the algorithm depends on the constraint that the edge weights are distinct in the graph. I suggest to remove that assumption and edit the content accordingly, i.e. the MST might not be unique.

[[User:Falcongl|Falcongl]] ([[User talk:Falcongl|talk]]) 20:37, 23 June 2013 (UTC)

:If the edge weights are not distinct then the algorithm can easily create cycles. E.g. suppose that the graph consists of three vertices a, b, and c, and three edges forming a triangle with all edge weights one. Then, suppose that a picks b as its nearest neighbor, b picks c, and c picks a. The result is not a tree. This can be fixed by using an appropriate tie-breaking rule, but that's essentially the same thing as forcing all edge weights to be distinct. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:48, 23 June 2013 (UTC)

::Thanks for the counter-example! I now see the need of distinctness: in step 7, if there are two edges with the same weight connecting two components, they might both get added to T under different components. If I may, I would like to add a short explanation for the necessity of the constraint after the pseudo-code. [[User:Falcongl|Falcongl]] ([[User talk:Falcongl|talk]]) 23:07, 23 June 2013 (UTC)

:::That sounds like a good idea. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 00:54, 24 June 2013 (UTC)

== Pseudocode ==

In my opintion the description given in pseudocode is wrong. It's confsuing when you mix things like that.

it says T is the set of nodes, but later you add edges to it, so you would have maybe in the beginning T = {A, B, C} and after adding edges you'd actually have T = {A, B, C, {A, B}}? That does not cover with what is done in the example.

[[Special:Contributions/141.53.220.30|141.53.220.30]] ([[User talk:141.53.220.30|talk]]) 14:07, 21 July 2013 (UTC)