1
$\begingroup$

Does someone know a proof for Camerinis Algorithm for finding a minimum bottleneck spanning tree?

To my knowledge its the only algorithm that performs in linear time to solve this task but I cant find a correctness prove for that.

https://stackoverflow.com/questions/22875799/how-to-compute-a-minimum-bottleneck-spanning-tree-in-linear-time

$\endgroup$
2
  • 1
    $\begingroup$ Have you looked Camerini's original paper "The min-max spanning tree problem and some extensions"? Google Scholar finds a pdf link. $\endgroup$
    – pcpthm
    Commented Feb 14 at 14:35
  • $\begingroup$ @pcpthm thanks! just looked it up and read it but it was kind of cryptic for me. By chance, did you get the idea of the proof? $\endgroup$
    – identicon
    Commented Feb 15 at 0:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.