1
Faculty of Mathematics, Shahrood University, Shahrood, Iran
2
Department of Mathematics, Hakim Sabzevari University, Sabzevar, Iran
Abstract
In this paper we study finding the $(k,l)$-core problem on a tree which the vertices have positive or negative weights. Let $T=(V,E)$ be a tree. The $(k,l)$-core of $T$ is a subtree with at most $k$ leaves and with a diameter of at most $l$ which the sum of the weighted distances from all vertices to this subtree is minimized. We show that, when the sum of the weights of vertices is negative, the $(k,l)$-core must be a single vertex. Then we propose an algorithm with time complexity of $O(n^2log n)$ for finding the $(k,l)$-core of a tree with pos/neg weight, which is in fact a modification of the one proposed by Becker et al. [Networks 40 (2002) 208].
Motevalli, S., Fathali, J., & Zaferanieh, M. (2016). An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree. Journal of Mathematical Modeling, 3(2), 129-144.
MLA
Samane Motevalli; Jafar Fathali; Mehdi Zaferanieh. "An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree". Journal of Mathematical Modeling, 3, 2, 2016, 129-144.
HARVARD
Motevalli, S., Fathali, J., Zaferanieh, M. (2016). 'An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree', Journal of Mathematical Modeling, 3(2), pp. 129-144.
VANCOUVER
Motevalli, S., Fathali, J., Zaferanieh, M. An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree. Journal of Mathematical Modeling, 2016; 3(2): 129-144.
)