درخت اشتاینر کمینه اقلیدسی درون چند ضلعی ساده با وجود موانع

سال انتشار: 1392
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 668

متن کامل این مقاله منتشر نشده است و فقط به صورت چکیده یا چکیده مبسوط در پایگاه موجود می باشد.
توضیح: معمولا کلیه مقالاتی که کمتر از ۵ صفحه باشند در پایگاه سیویلیکا اصل مقاله (فول تکست) محسوب نمی شوند و فقط کاربران عضو بدون کسر اعتبار می توانند فایل آنها را دریافت نمایند.

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

TIAU01_364

تاریخ نمایه سازی: 14 شهریور 1393

چکیده مقاله:

مسئله درخت اشتاینر منجر به راه حل هایی در زمینه علمی و تجاری مختلف شده است که مسیر یابی شبکه های کامپیوتری و مدارهای مجتمع الکترونیکی از آن جمله هستند . زمینه های محاسباتی این مسئله ،آن راتبدیل به یک موضوع مهم تحقیقاتی در هندسه محاسباتی کرده است . با در نظر گرفتن چند نقطه در صفحه اقلیدسی که به این نقاط ترمینال گویند یک درخت پوشای مینیمم بدست می آید که این نقاط را به هم متصلمی کند به این درخت یکسری نقاط دیگر (نقاط اشتاینر ) اضافه می شود که باعث کوتاهتر شدن طول درخت می شود که به درخت حاصل ،درخت اشتاینر کمینه اقلیدسی می گویند . این مسئله به عنوان مسئلهNP_hard در نظر گرفته می شود. با در نظر گرفتن چند ضلعی ساده p با m راس وn ترمینال درآن سعی می گردد یک درخت کمینه اشتاینر اقلیدسی پیدا شود که به همهn ترمینال موجود درp متصل باشد. در این مقاله ما راه حلی برای چند ترمینال در یک چند ضلعی ساده با وجود موانع پیشنهاد کر ده ایم

کلیدواژه ها:

درخت اشتاینر ، درخت اشتاینر کمینه اقلیدسی ، مثلث بندی دلونوی ، چند ضلعی ساده

نویسندگان

و خسروی نژاد

دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین

ع باقری

دکترای کامپیوتر عضو هیئت علمی دانشگاه امیرکبیر

م کیوان پور

دکترای کامپیوتر عضو هیئت علمی دانشگاه آزاد قزوین

ع خسروی نژاد

دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین