چکیده

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

فهرست مطالب

1-مقدمه

2-مقدمات

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

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

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

6-مراجع