|
|
 | | From: | Joe | | Subject: | Who can prove Boruvka's algorithm ? | | Date: | 19 Jan 2005 10:13:12 -0800 |
|
|
 | Hi,
Who can give a formal prove of the correctness of Boruvka's algorithm
for finding the Minimum Spanning Tree?
Thanks !
|
|
| | From: | J.H.Jongejan | | Subject: | Re: Who can prove Boruvka's algorithm ? | | Date: | Thu, 20 Jan 2005 15:11:52 +0100 |
|
|
| Joe wrote:
> Hi,
>
> Who can give a formal prove of the correctness of Boruvka's algorithm
> for finding the Minimum Spanning Tree?
>
> Thanks !
Hi Joe,
I found a paragraph on the correctness (not in a formal way) in
Algorithm Design, Goodrich/Tamassia, page 370. By the way, the inventor
of this algorithm is called Baruvka, with a small open circle above
the 'o'.
With regards,
Jan Jongejan
Dept. Comp.Sci.,
Univ. of Groningen,
Netherlands.
|
|
|
