On the finding 2-(k,l)-core of a tree with arbitrary real weight

Iranian Journal of Numerical Analysis and Optimization

مقاله 5، دوره 9، شماره 1 - شماره پیاپی 15، 2019، صفحه 93-104   

نوع مقاله: Research Article

شناسه دیجیتال (DOI): 10.22067/ijnao.v9i1.65852

نویسندگان

S. M. Ashkezari؛ J. Fathali^*

Shahrood University of Technology, University Blvd., Shahrood, Iran.

چکیده

Let T = (V, E) be a tree with | V |= n. A 2-(k, l)-core of T is two subtrees with at most k leaves and with a diameter of at most l, which the sum of the distances from all vertices to these subtrees is minimized. In this paper, we first investigate the problem of finding 2-(k, l)-core on an unweighted tree and show that there exists a solution that none of (k, l)-cores is a vertex. Also in the case that the sum of the weights of vertices is negative, we show that one of (k, l)-cores is a single vertex. Then an algorithm for finding the 2-(k, l)-core of a tree with the pos/neg weight is presented.

کلیدواژه‌ها

core؛ Facility location؛ Median subtree؛ Semi-obnoxious

مراجع