Two paths location of a tree with positive or negative weights

• This paper studies two problems of locating two paths in weighted trees.
• We provide an algorithm in time O(n2)O(n2) by the optimal properties for the one problem.
• We provide an algorithm in time O(n3)O(n3) for the other problem.

This paper studies two problems of locating two paths in a tree with positive and negative weights. The first problem has objective to minimize the sum of minimum weighted distances from every vertex of the tree to the two paths, while the second is to minimize the sum of the weighted minimum distances from every vertex of the tree to the two paths. We develop an O(n2)O(n2) algorithm based on the optimal properties for the first problem, and also an O(n3)O(n3) algorithm for the second problem.