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 degree $1$
  2. internal vertices have degree $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 this 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

Your Answer

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

Browse other questions tagged or ask your own question.