|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|