یک الگوریتم خطی برای مساله پیداکردن هسته درخت های بازه ای وزن دار
|
|
|
|
|
|
|
|
نویسنده
|
متولی اشکذری سمانه ,فتحعلی جعفر
|
|
منبع
|
تحقيق در عمليات در كاربردهاي آن - دانشگاه آزاد اسلامي لاهيجان - 1395 - دوره : 13 - شماره : 2 - صفحه:101 -111
|
|
|
|
|
چکیده
|
در این مقاله ابتدا گراف های بازه ای را تعریف و سپس مساله ی پیداکردن هسته روی گراف های بازه ای و درخت های بازه ای را بررسی می کنیم. یک هسته در یک گراف بازه ای، مسیری از بازه های متصل به هم است که مجموع فاصله های تمام بازه ها تا این مسیر کمینه شود. نشان می دهیم بازه هایی که روی هسته ی یک درخت قرار دارند نمی توانند بازه ای غیر ماکسیمال باشند. سپس الگوریتمی با پیچیدگی زمانی o(n) برای پیداکردن هسته ی یک درخت بازه ای ارائه می دهیم.
|
|
کلیدواژه
|
گراف بازه ای، هسته درخت، مکانیابی
|
|
آدرس
|
دانشگاه صنعتی شاهرود, ایران, دانشگاه صنعتی شاهرود, ایران
|
|
پست الکترونیکی
|
fathali@shahroodut.ac.ir
|
|
|
|
|
|
|