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 -core problem on a tree which the vertices have positive or negative weights. Let be a tree. The -core of is a subtree with at most leaves and with a diameter of at most 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 -core must be a single vertex. Then we propose an algorithm with time complexity of for finding the -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. and Zaferanieh, M. (2016). An efficient algorithm for finding the semi-obnoxious -core of a tree. Journal of Mathematical Modeling, 3(2), 129-144.
MLA
Motevalli, S. , , Fathali, J. , and Zaferanieh, M. . "An efficient algorithm for finding the semi-obnoxious -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 -core of a tree', Journal of Mathematical Modeling, 3(2), pp. 129-144.
CHICAGO
S. Motevalli , J. Fathali and M. Zaferanieh, "An efficient algorithm for finding the semi-obnoxious -core of a tree," Journal of Mathematical Modeling, 3 2 (2016): 129-144,
VANCOUVER
Motevalli, S., Fathali, J., Zaferanieh, M. An efficient algorithm for finding the semi-obnoxious -core of a tree. Journal of Mathematical Modeling, 2016; 3(2): 129-144.