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:
- tips have degree $1$
- 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