دوره 13، شماره 2 - ( 5-1395 )                   جلد 13 شماره 2 صفحات 111-101 | برگشت به فهرست نسخه ها

XML English Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

A Linear Algorithm for Finding Core of Weighted Interval Trees. jor 2016; 13 (2) :101-111
URL: http://jamlu.liau.ac.ir/article-1-1412-fa.html
متولی اشکذری سمانه، فتحعلی جعفر. یک الگوریتم خطی برای مساله ی پیداکردن هسته ی درخت های بازه ای وزندار. تحقیق در عملیات در کاربردهای آن. 1395; 13 (2) :101-111

URL: http://jamlu.liau.ac.ir/article-1-1412-fa.html


دانشگاه صنعتی شاهرود، دانشکده علوم ریاضی، شاهرود
چکیده:   (3774 مشاهده)

در این مقاله ابتدا گراف های بازه ای را تعریف و سپس مسأله ی پیداکردن هسته روی گراف های بازه ای و درخت های بازه ای را بررسی می کنیم. یک هسته در یک گراف بازه ای، مسیری از بازه های متصل به هم است که مجموع فاصله های تمام بازه ها تا این مسیر کمینه شود. نشان می دهیم بازه هایی که روی  هسته ی یک درخت  قرار دارند نمی توانند بازه ای غیر ماکسیمال باشند. سپس الگوریتمی با پیچیدگی زمانی o(n) برای پیداکردن هسته ی یک درخت بازه ای ارائه می دهیم.

واژه‌های کلیدی: گراف بازه ای، هسته درخت، مکانیابی
متن کامل [PDF 639 kb]   (1233 دریافت)    
نوع مطالعه: پژوهشي | موضوع مقاله: تخصصي
دریافت: 1395/10/4 | پذیرش: 1395/10/4 | انتشار: 1395/10/4

ارسال نظر درباره این مقاله : نام کاربری یا پست الکترونیک شما:
CAPTCHA

بازنشر اطلاعات
Creative Commons License این مقاله تحت شرایط Creative Commons Attribution-NonCommercial 4.0 International License قابل بازنشر است.