ع خسروی نژاد - دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین
ع باقری - دکترای کامپیوتر عضو هیئت علمی دانشگاه امیرکبیر
م کیوان پور - دکترای کامپیوتر عضو هیئت علمی دانشگاه آزاد قزوین
خسروی نژاد - دانشجو کارشناسی ارشد کامپیوتر دانشگاه آزاد قزوین

مسئله درخت اشتاینر، عبارت است از پیدا کردن درخت کمینه ای که شامل نقاط مشخصی باشد و در صورت لزوم از تعدادی نقاط کمکی نیز برای کمینه کردن طول درخت استفاده کند.دراین مقاله درخت اشتاینر درحالتی بررسی شده است که رئوس و یالهای درخت در داخل یک چند ضلعی متعامد قرار گرفته اند. این مسئله در طراحی خطوط نفت و بزرگراه ها و طراحی مدارات مجتمع الکترونیکی کاربرد بسیاری دارد. این مسئله Np-hardبوده و الگوریتمی تا کنون با زمان چندجمله ای برای آن شناخته نشده است .دراین مقاله الگوریتمی برای ساخت درخت اشتاینر با استفاده از گراف پیشنهاد شده است و در برخی موارد به جواب های بهینه رسیده ایم.

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