أقصى نسخة تغطية من مجموعة المهيمنة

Question

مشكلة المهيمنة هي:

بالنظر إلى $ n $ vertex graph $ g= (v، e) $ ، ابحث عن تعيين $ s (\ subseteq v) $ مثل $ | N [S] | $ هو بالضبط < Span Class="حاوية الرياضيات"> $ n $ ، حيث $$ N [S]:={x ~ | \ Text {إما $ × $ أو جارة من $ x $ تكمن في $ S $} \} $

سؤالي هو إذا كان لديك اسم جديد (مشكلة جديدة) اسم محدد في الأدب، وإذا لم يكن ما يجب أن يكون الاسم الأكثر ملاءمة.

مشكلة جديدة: بالنظر إلى $ n $ vertex graph $ g= (v، ه) $ وعدد صحيح $ K $ ، ابحث عن مجموعة $ s (\ subseteq v) $ < / SPAN> الحجم $ k $ مثل $ | n [s] | $ تم تعظيمها. < / ص>

للمشكلة الثانية، بعض الأسماء التي رأيتها في الأدبيات هي تغطية الرسم البياني القصوى؛ التغطية الجزئية؛ K-Dementating-set، (ومع ذلك، تستخدم نفس الأسماء بالضبط في السياقات الأخرى).

Answer 1

المشكلة التي يجب أن تختار فيها $ k $ ، تعزز عدد القمم التي يهيمن عليها المعروفة باسم المشكلة الميزانية المحددة المشكلة وبعد تتم دراسة المشكلة أو المتغير المتصل على الأقل من قبل لامبرو، Sigalis و Zissimopoulos [1] و KHULLER، PUROHIT و SARPATWAR [2]. كما يظهر في الاستطلاع الأخير من Narayanaswamy و Vijayaragunathan [3].

---

[1] Lamprou، ioannis، ioannis Sigalas، و vassilis zissimopoulos. "تحسين الهيمنة المتصلة المدرجة في الميزانية والهيمنة على الحافة المدرجة في الميزانية." ARXIV Preprint Arxiv: 1907.06576 (2019).

[2] Khuller، سمير، مانيش بوروهيت، و Kanthi K. Sarpatwar. "تحليل الحي الأمثل: خوارزميات للمتنزه المدرجة في الميزانية والجزئية المتصلة بالسيطرة على مشاكل المحددة". وقائع ندوة سنويا السنوية الخامسة والعشرين على الخوارزميات المنفصلة. جمعية الرياضيات الصناعية والتطبيقية، 2014.

[3] <3] Narayanaswamy، N. S، و R. Vijayaragunathan. "التحسين المعلمات في الرسوم البيانية غير المؤكدة - دراسة استقصائية وبعض النتائج". خوارزميات 13.1 (2020): 3.