پیوندهای مفید
آمار
| تعداد نشریات | 31 |
| تعداد شمارهها | 708 |
| تعداد مقالات | 6,652 |
| تعداد مشاهده مقاله | 9,191,306 |
| تعداد دریافت فایل اصل مقاله | 6,304,982 |
An efficient algorithm for finding the semi-obnoxious $(k,l)$-core of a tree | ||
| Journal of Mathematical Modeling | ||
| مقاله 2، دوره 3، شماره 2، خرداد 2016، صفحه 129-144 اصل مقاله (469.58 K) | ||
| نوع مقاله: Research Article | ||
| نویسندگان | ||
| Samane Motevalli1؛ Jafar Fathali* 1؛ Mehdi Zaferanieh2 | ||
| 1Faculty of Mathematics, Shahrood University, Shahrood, Iran | ||
| 2Department of Mathematics, Hakim Sabzevari University, Sabzevar, Iran | ||
| چکیده | ||
| 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]. | ||
| کلیدواژهها | ||
| Core؛ Facility location؛ Median subtree؛ Semi-obnoxious | ||
|
آمار تعداد مشاهده مقاله: 2,228 تعداد دریافت فایل اصل مقاله: 1,866 |
||