1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Would you accept a counterexample as an answer? $\endgroup$ – John L. Nov 29 '19 at 22:44

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.