Talk:Borůvka's algorithm

From Wikipedia, the free encyclopedia

 This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start rated as Start-Class on the assessment scale
Mid rated as Mid-importance on the assessment scale

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 ů - if that were valid HTML, which it is not!

If someone knows how to do this then feel free to correct the text.

Done. (Copied from minimum spanning tree, actually.) grendel|khan 01:03, 2004 Jun 5 (UTC)

The algorithm given here is not very well expressed. It is hard to find one which is a good description - David Eppstein's (from U. Irvine) is not bad (see http://www.ics.uci.edu/~eppstein/161/960206.html ), though the descriptions from http://www2.toki.or.id/book/AlgDesignManual/LEC/LECTURES/ALL.HTM may be better.

I think the pseudocode I've put down is pretty readable. Maybe I'll convert it to C or Perl or something. grendel|khan 01:03, 2004 Jun 5 (UTC)
Yes, it's quite readable. Andris 01:12, Jun 5, 2004 (UTC)

"...as a method of efficiently electrifying Bohemia."

maybe it's just me, but what meaning of the word Bohemia is assumed here? can somebody clear up this sentance?
The region, of course. What other Bohemia is there? Click the link to find out more. "Electrifying" is a bit confusing; I will take a crack at that. Deco 10:39, 16 Jan 2005 (UTC)
I'm not sure if it was actually Bohemia in this case, rather than Moravia, having considered that Borůvka lived and worked in Brno, the capital of Moravia. Unfortunately outside the Czech Republic, there is a strong tendency to use the name Bohemia to refer to the Czech Republic as a whole, not just to the historical land. Unfortunately, though, I was not able to find any online resource proving this assumption - so I can base only on what my lecturer has told here at the Faculty of informatics at the Masaryk University in Brno. Is there someone who could give a source to confirm that it was actually in Bohemia (i.e. in the region around Prague)? Blahma 15:06, 24 May 2006 (UTC)
I think that you are probably right about Moravia. Dr. Nesetril form Charles Uni (who knew Boruvka personally and knew some first-hand stories about this algorithm) once mentioned that it was northern Moravia that they wanted to electrify. I didn't ask him how sure he was about this piece of information, though. —Preceding unsigned comment added by 74.136.208.121 (talk) 02:37, August 29, 2007 (UTC)
Actually, southern Moravia (sorry about that). At least according to Kapitoly z diskretni matematiky by Matousek and Nesetril, which cites "Nekolik vzpominek na matematicky zivot v Brne" in Pokroky mat. fyz. a astr. 22 (1997) 91-99. —Preceding unsigned comment added by 74.136.215.67 (talk) 03:35, 8 September 2007 (UTC)

[edit] Florek and his co-authors were anthropologists

This is very controversial ;) I don't know about Florek but coauthors were mathematicians. In 1951 they were professors at universities: Steinhaus, Zubrzycki and Perkal in Wrocław/Poland and Łukasiewicz in Dublin

I found that Kazimierz Florek is a member of Polish Mathematical Society - currently he lives in USA. I'm going to ask of his descendand in Wrocław to check an authorship of 1951 articles.

I've got e-mail from dr Jan Florek (Kazimierz's son). Kazimierz is coauthor of both articles. In 1951 he was an assistant of prof. Hugo Steinhas (Mathematical Faculty of Wrocław University) and prof. Roman Stanisław Ingarden (Physical Faculty). In '60s he worked as an IT consultant in the industry.

Why is there no mention of Yao's improvement to make this algorithm O(log log n)? 129.59.32.191 01:19, 11 February 2007 (UTC)