زیرگراف های کامل یک گراف

[black.meshki]

با سلام
واسه یکی از قسمتهای پروژه های درسیم به یک مشکلی برخورد کردم که متاسفانه تا این مساله حل نشه پروژه جلو نمیره
میخوام یک کدی بنویسم که از روی ماتریس همجواری بتونه بزرگترین زیرگرافهای کامل اون گراف رو دربیاره
کمکی که از شما میخوام اینه که یک الگوریتم کلی به من بدید
به علت اینکه تعداد رئوس بالاست حدود 4000 باید الگوریتم بهینه باشه باشه ( مثل الگوریتم های حریصانه greedy نبود هم مشکلی نیست اما همه راه حل های ممکن چک نشه )
خودم هر چی رو مساله فکر می کنم می بینم فضای مساله یکم بزرگه و می بینم راهی به جز بررسی کردن تمام راه حل های ممکن وجود نداره
ماتریس همجواری این جوری هست که مثلا 3 تا راس a , b , c داریم که همه به هم وصل هستن ( شکل گرافش عین مثلث میشه )
ماتریس همجواری برای این مثال اینجوری
abc
a011
b101
c110

از راس a به راس a رابطه نیست پس میشه صفر
از راس a به راس b رابطه هست پس میشه یک
و الی آخر

گراف کامل هم گرافیه که از همه رئوس به رئوس دیگر با یک یال ( خط ) متصل باشه

در ضمن برای تشخیص گراف کامل از روی ماتریس همجواری همه درایه های ماتریس به جز درایه های روی قطر اصلی باید یک باشه
لطفاً سورس کد نذارید و اگر می تونید در نحوه یاده سازی الگوریتمش کمکم کنید
امیدوارم بتونید کمکم کنید

با سپاس ...

[hadi0x7c7]

شما یه نیگاه به اینجا بنداز http://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph

[black.meshki]

شما یه نیگاه به اینجا بنداز http://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph

ممنون از توجهتون
اتفاقاً منم میخوام روش خوشه بندی clique که از روش های graph partitioning هست رو پیاده سازی کنم نمی دونستم این مسأله یک مسأله np-complete هست
یعنی یک جورایی هیچ راهی برای پیاده سازی وجود نداره درسته ( اگرم وجود داشته باشه هنوز کشف نشده ) ؟
دوستان اگر راه حلی به ذهنشون میرسه دریغ نکنن