MAX Clique في الرسم البياني الفاصل

Question

وفقا ل خوارزميات فعالة للرسوم البيانية الفاصلة والرسوم البيانية القوسية الدائرية هناك $ o (n \ log n) $ الخوارزمية للعثور على MAX Clique في رسم بياني فاصل، على افتراض أن لديك نموذج الفاصل الزمني. لسوء الحظ، لا توجد الورقة ولا المراجع التي توضحها بالفعل الخوارزمية، بما يتجاوز القول أنه يمكنك تعديل الخوارزمية المعروفة لرسوم البيان الفاصل الزمني للألوان الأمثل (حيث تلون اللون الجشبي باللون الرسم البياني في الترتيب الناتج عن فرز الفواصل الزمنية المعجمية) إلى حساب ماكس زمرة. هذا منطقي، حيث أن أكبر لون يستخدم في التلوين الأمثل هو حجم زمرة MAX في رسم بياني مثالي (ورسم رسوم بيانية فاصلة مثالية). لسوء الحظ، أبعد من ذلك، فقدت ما إذا كنت لحساب زمرة ماكس. النهج الواضح هو تعديل بعض هيكل البيانات في كل مرة يزداد فيها أقصى اللون، لكن لا يمكنني معرفة هيكل البيانات بالضبط أو كيفية تعديله.

هل يعرف أي شخص مرجعا لهذه الخوارزمية أو يمكنه إعادة اختراع وصفها؟

Answer 1

الرسوم البيانية الفاصل هي الرسوم البيانية Chordal، بحيث يمكنك استخدام خوارزمية وقت خطي لإيجاد MAX Clique في رسم بياني Chordal.يمكن القيام بذلك عن طريق العثور على طلب إلغاء مثالي أولا، ثم باستخدام حقيقة أنه في كل مرة يتم فيها القضاء على رأسها، فإنها تشكل زهرة مع جيرانها غير القضاء عليها حتى الآن.علاوة على ذلك، تظهر جميع العصابات القصوى في هذه العملية.

للعثور على طلب القضاء المثالي، والحد الأقصى للبحث عن الكابلات (MCS) هو أبسط خوارزمية ويعمل في الوقت الخطي.(لا أعرف لماذا يذكر Wikipedia Lexbfs أولا، إنه أكثر تعقيدا.)

Answer 2

giveacodicetagpre.

أعتقد أن هذا هو التنفيذ الصحيح بناء على خوارزمية التلوين الفاصل التي تعمل في $ O (n \ log n) $ الوقت.

إذا كنت تهتم فقط في Clique Max، فيمكن تبسيطه قليلا:

giveacodicetagpre.