عنوان ترجمه شده مقاله: ارائه یک الگوریتم با پیچیدگی زمانی چند جمله ای جهت حل مسأله زیرگراف متصل مشترک با بیشترین یال برای گراف های مسطح بیرونی با درجه محدود

چکیده

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

فهرست مطالب

1-مقدمه

2-مقدمات

3-الگوریتمی برای یک حالت محدود

4-الگوریتمی برای گراف­ های مسطح بیرونی با درجه محدود

5-نتیجه­ گیری

6-مراجع