|
|
|
|
On the Finding 2-(K,L)-Core of A Tree With Arbitrary Real Weight
|
|
|
|
|
|
|
|
نویسنده
|
Ashkezari S.M. ,Fathali J.
|
|
منبع
|
Iranian Journal Of Numerical Analysis And Optimization - 2019 - دوره : 9 - شماره : 1 - صفحه:93 -104
|
|
|
|
|
چکیده
|
Abstract 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.
|
|
آدرس
|
Shahrood University Of Technology, Faculty Of Mathematical Sciences, ایران, Shahrood University Of Technology, Faculty Of Mathematical Sciences, ایران
|
|
پست الکترونیکی
|
fathali@shahroodut.ac.ir
|
|
|
|
|
|
|
|
|
|
|
|
|
|
مساله پیدا کردن –(k, l) − ٢هسته روی درختهای با وزن حقیقی
|
|
|
|
|
Authors
|
فتحعلی جعفر ,متولی اشکذری سمانه
|
|
Abstract
|
فرض کنید (T = (V, Eدرختی شامل nراس باشد. یک –(k, l)− ٢هسته از درخت Tشامل دو زیر درخت مجزا از Tمی باشد که هر یک از آنها حداکثر دارای Tبرگ و حداکثر قطر lهستند، همچنین مجموع فاصله تمام رئوس درخت تا این دو زیردرخت کمینه است. در این مقاله در ابتدا به بررسی مساله پیدا کردن –(k, l) − ٢هسته روی درختی که در آن وزن تمام رئوس یکسان است می پردازیم و نشان می دهیم جوابی برای این مساله وجود دارد که هیچ یک از هسته ها یک راس تنها نیست. سپس الگوریتمی برای پیدا کردن –(k, l) − ٢هسته روی درختهایی که وزن رئوس آنها می تواند مثبت یا منفی باشد، ارائه می دهیم.
|
|
Keywords
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|