TY - JOUR
ID - 1217
TI - An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree
JO - Journal of Mathematical Modeling
JA - JMM
LA - en
SN - 2345-394X
AU - Motevalli, Samane
AU - Fathali, Jafar
AU - Zaferanieh, Mehdi
AD - Faculty of Mathematics, Shahrood University, Shahrood, Iran
AD - Department of Mathematics, Hakim Sabzevari University, Sabzevar, Iran
Y1 - 2016
PY - 2016
VL - 3
IS - 2
SP - 129
EP - 144
KW - Core
KW - Facility location
KW - Median subtree
KW - Semi-obnoxious
DO -
N2 - 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].
UR - https://jmm.guilan.ac.ir/article_1217.html
L1 - https://jmm.guilan.ac.ir/article_1217_decabc127c158c47e815e39eb31e5c64.pdf
ER -