1
vote
2answers
53 views

When trees are the answer: what is the question?

For which optimization problems are (abstract) trees the best solution? E.g. binary search trees are somehow optimal data structures for quick search. But why for example do botanic trees grow as ...
2
votes
2answers
42 views

Finding an Isolated Maximum subset of tree

Given an Oriented Tree T(V,E) with n nodes, each node have an non-negative number (the numbers are not related to nodes order). A subgroup Z of V called an Isolated if it doesn't include two nodes ...
0
votes
0answers
12 views

Which cut-off for collapsing this tree?

I have a Newick tree that is built by comparing similarity (euclidean distance) of Position Weight Matrices (PWMs or PSSMs) of DNA regulatory motifs that are ~5-9 bp long sequences. An interactive ...
0
votes
0answers
62 views

Linear constraints on distance (hop) matrix of a tree

I have an optimization problem where I want the constraints to be linear. The variables are elements of an $N\times N$ matrix D. The elements of D, ie $D(i,j)$ are integers and represent the number of ...
2
votes
1answer
1k views

Show that Minimum Spanning Tree is unique

Show that MST is unique in case the edge weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example by contradiction, saying that we ...
0
votes
0answers
48 views

An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label). We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...