Let $G=(V,E)$ be a simple graph with weights $w_{ij}$ (can be assumed to be positive). Is it possible to find the minimum (or maximum) weight, rooted spanning tree that is binary? That means every node has a degree at most 3, which would correspond to a parent and two children?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Would you accept a counterexample as an answer? $\endgroup$– John L.Nov 29, 2019 at 22:44
Add a comment
|