Given a graph $G$ with $n$ tip vertices, $n-2$ internal vertices, and a cost on each edge $C(v)$, find a minimum spanning tree subject to degree constraints:

  1. tips have a degree of $1$
  2. internal vertices have a degree of $3$.

There are no edges between pairs of tips in the given graph. These constraints ensure an unrooted binary tree forms.

I thought to use the following algorithm, which I based off Prim's algorithm:

For n-2 iterations:
    Find the pair of edges i and j neighbouring a single internal vertex that minimises the cost C(i)+C(j)
    Add edges i and j to the tree
  • $\begingroup$ @wajaap, please check the difference between minimize and minimise. $\endgroup$
    – John L.
    Jan 26 at 0:05
  • $\begingroup$ @wajaap I voted to approve your edit. However, there is no need to change "neighbouring" to "neighboring" next time, even if you are in strong support of (the English used in) United States of America. Check this article. $\endgroup$
    – John L.
    Jan 26 at 0:08


Your Answer

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