On the finding 2-(k,l)-core of a tree with arbitrary real weight

Abstract

Let T = (V, E) be a tree with | V |= n. A 2-(k, l)-core of T is two subtrees with at most k leaves and with a diameter of at most l, which the sum of the distances from all vertices to these subtrees is minimized. In this paper, we first investigate the problem of finding 2-(k, l)-core on an unweighted tree and show that there exists a solution that none of (k, l)-cores is a vertex. Also in the case that the sum of the weights of vertices is negative, we show that one of (k, l)-cores is a single vertex. Then an algorithm for finding the 2-(k, l)-core of a tree with the pos/neg weight is presented.

Keywords

• core
• facility location
• median subtree
• semi-obnoxious