An efficient algorithm for finding the semi-obnoxious (k,l)-core of a tree
Publish place: Journal of Mathematical Modeling، Vol: 3، Issue: 2
Publish Year: 1395
نوع سند: مقاله ژورنالی
زبان: English
View: 14
This Paper With 16 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_JMMO-3-2_002
تاریخ نمایه سازی: 19 خرداد 1403
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^۲log 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 ۴۰ (۲۰۰۲) ۲۰۸].
Keywords:
Authors
Samane Motevalli
Faculty of Mathematics, Shahrood University, Shahrood, Iran
Jafar Fathali
Faculty of Mathematics, Shahrood University, Shahrood, Iran
Mehdi Zaferanieh
Department of Mathematics, Hakim Sabzevari University, Sabzevar, Iran