0
$\begingroup$

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it?

I can't seem to think of a way to make a distinction between the same weights, it feels unnatural.

$\endgroup$
3
$\begingroup$

Though the Borůvka's algorithm (wiki) for minimum spanning tree is (sometimes? often?) described for weighted graphs with distinct edge weights, this treatment is only for convenience.

If we have an algorithm that assumes the edge weights are unique, we can use it on graphs where multiple edges have the same weight, as long as we have some way of breaking the ties. For example, in graphs where edges have identical weights, edges with equal weights can be ordered based on the lexicographic order of their endpoints (suggested by the wiki article).

To apply the lexicographic order, assume two edges $(a,b)$ and $(c,d)$ have the same weight $w(a,b) = w(c,d)$, where $a,b,c,d$ are (not necessarily distinct) vertices. Then we can decide which of $w(a,b)$ and $w(c,d)$ have the "smaller" weight by comparing the pair $(a,b)$ and $(c,d)$ in their lexicographic order.

Therefore, you don't need to re-weight the equally-weighted edges. You only need to mark them distinct.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How would you implement the lexicographic order for a graph? $\endgroup$ – Milan Jan 26 '15 at 5:09
  • 1
    $\begingroup$ @Milan See my update. $\endgroup$ – hengxin Jan 26 '15 at 5:17
  • $\begingroup$ Thank you for this useful clarification! Somehow I was unable to see a similar explanation of the need of the "just tie breaking resolver" rather than true unique graph weights. $\endgroup$ – Igor Soloydenko Jun 4 '18 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.