Command Palette
Search for a command to run...
(1,1)-تحرير الكластر قابل للحل في وقت متعدد الحدود
(1,1)-تحرير الكластر قابل للحل في وقت متعدد الحدود
Gregory Gutin; Anders Yeo
الملخص
الرسوم البيانية H تعتبر رسومًا كليكيًا إذا كانت H اتحادًا غير متقاطع للرؤوس من الكليكات. قدم أبو خزام (2017) مشكلة (a,d)-{تحرير التجمعات}، حيث لعددين طبيعيين ثابتين a,d، يُعطى رسم بياني G وأوزان الرؤوس a: V(G)→0,1,…,a وd: V(G)→0,1,…,d، ويتعين علينا تحديد ما إذا كان يمكن تحويل G إلى رسم تجمعي عن طريق حذف ما لا يزيد على d(v) من الحواف المتصلة بكل رأس v∈V(G) وإضافة ما لا يزيد على a(v) من الحواف المتصلة بكل رأس v∈V(G). نتائج كوموسيفيتش وأولمان (2012) وأبو خزام (2017) قدّمت تصنيفًا للتعقيد (في P أو NP-كاملة) لمشكلة (a,d)-{تحرير التجمعات} لكل زوجي العددين a,d باستثناء حالة a=d=1. تخمين أبو خزام (2017) أن مشكلة (1,1)-{تحرير التجمعات} تنتمي إلى P. نحن نحل هذا التخمين بشكل إيجابي من خلال: (i) تقديم سلسلة من خمس عمليات تقليل متعددة الحدود إلى رسوم بيانية خالية من الدورات الطولية 3 و4 (C3-free وC4-free) ذات الدرجة القصوى لا تتجاوز 3، و(ii) تصميم خوارزمية متعددة الحدود لحل مشكلة (1,1)-{تحرير التجمعات} في رسوم بيانية خالية من الدورات الطولية 3 و4 (C3-free وC4-free) ذات الدرجة القصوى لا تتجاوز 3.