Optimal cuts and partitions in tree metrics in polynomial time
We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one-dimensional geometric metric settings. Our method of solution could be also of independent interest in other applications. We discuss also an extension of our method t
