Maximum Product Spanning Tree

Question

Consider problem similar to a minimum or maximum spanning tree, but instead we want to find the maximum product spanning tree, that is a tree that maximums the product of weights of the edges. Describe an efficient algorithm to find the maximum product spanning tree.  

[Assume each edge weight is at least 1.]

Answer 1

If w1 w2 w3  is maximized, then log w1 + log w2 + log w3 is maximized.

So, if we replace each w1 with its log value, and then find the maximum weight spanning tree, that is like finding maximum product spanning tree for the original tree.

Comments

Adding to that, can we also assert that if logw1 + logw2 + logw3 is maximized then w1 + w2 + w3 is also maximized? Concluding that MPST is the same as MST?

---

No, that statement (logw1 + logw2 + logw3 is maximized then w1 + w2 + w3 is also maximized) is not relevant for this question.  Product of edge weights is maximized <=> Sum of logs of edge weights is maximized.

Answer 2

​If the product  w1*w2*w3 is at its maximum, then the sum log(w1) + log(w2) + log(w3) is also at its maximum due to the logarithmic property. Therefore, substituting each w1 with its logarithmic value and determining the maximum weight spanning tree is similar to discovering the maximum product spanning tree in the original tree.