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

Revision as of 13:57, 12 October 2010

Latest revision as of 23:37, 8 March 2024

(19 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: ==

This page refers the original papers by Otakar Borůvka and Gustave Choquet, but lacks references to the paper by

Florek, Łukasiewicz, Perkal, Steinhaus, and Zubrzycki and the paper by Sollin. Also, it is mentioned its use in parallel computing but there is not a reference to who first implemented in in parallel or any papers about parallel implementations.

<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)

----

Note that Otakar Boruvka's name should really be spelled with a special character, but this is not one of the standard ones on the typewriter keyboard, nor is it in the HTML special character set. The u should have a small circle over the top - equivalent to &uring; - if that were valid HTML, which it is not!

Line 114 ⟶ 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)