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

Let T = (V, E) be a tree with V = n. A 2-(k, 1)-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, 1)-core on an unweighted tree and show that there exists a solution that none of (k, 1)-cores is a vertex. Also in the case that the sum of the weights of vertices is negative, we show that one of (k, 1)-cores is a single vertex. Then an algorithm for finding the 2-(k, 2)-core of a tree with the pos/neg weight is presented

Keywords:

Core , Facility location , Median subtree , Semi-obnoxious