HyperAIHyperAI

Command Palette

Search for a command to run...

(1,1)-تحرير الكластر قابل للحل في وقت متعدد الحدود

Gregory Gutin; Anders Yeo

الملخص

الرسوم البيانية HHH تعتبر رسومًا كليكيًا إذا كانت HHH اتحادًا غير متقاطع للرؤوس من الكليكات. قدم أبو خزام (2017) مشكلة (a,d)(a,d)(a,d)-{تحرير التجمعات}، حيث لعددين طبيعيين ثابتين a,da,da,d، يُعطى رسم بياني GGG وأوزان الرؤوس a: V(G)0,1,,aa^:\ V(G)\rightarrow {0,1,\dots, a}a: V(G)0,1,,a وd: V(G)0,1,,dd^:\ V(G)\rightarrow {0,1,\dots, d}d: V(G)0,1,,d، ويتعين علينا تحديد ما إذا كان يمكن تحويل GGG إلى رسم تجمعي عن طريق حذف ما لا يزيد على d(v)d^(v)d(v) من الحواف المتصلة بكل رأس vV(G)v\in V(G)vV(G) وإضافة ما لا يزيد على a(v)a^(v)a(v) من الحواف المتصلة بكل رأس vV(G)v\in V(G)vV(G). نتائج كوموسيفيتش وأولمان (2012) وأبو خزام (2017) قدّمت تصنيفًا للتعقيد (في P أو NP-كاملة) لمشكلة (a,d)(a,d)(a,d)-{تحرير التجمعات} لكل زوجي العددين a,da,da,d باستثناء حالة a=d=1a=d=1a=d=1. تخمين أبو خزام (2017) أن مشكلة (1,1)(1,1)(1,1)-{تحرير التجمعات} تنتمي إلى P. نحن نحل هذا التخمين بشكل إيجابي من خلال: (i) تقديم سلسلة من خمس عمليات تقليل متعددة الحدود إلى رسوم بيانية خالية من الدورات الطولية 3 و4 (C3C_3C3-free وC4C_4C4-free) ذات الدرجة القصوى لا تتجاوز 3، و(ii) تصميم خوارزمية متعددة الحدود لحل مشكلة (1,1)(1,1)(1,1)-{تحرير التجمعات} في رسوم بيانية خالية من الدورات الطولية 3 و4 (C3C_3C3-free وC4C_4C4-free) ذات الدرجة القصوى لا تتجاوز 3.


بناء الذكاء الاصطناعي بالذكاء الاصطناعي

من الفكرة إلى الإطلاق — سرّع تطوير الذكاء الاصطناعي الخاص بك مع المساعدة البرمجية المجانية بالذكاء الاصطناعي، وبيئة جاهزة للاستخدام، وأفضل أسعار لوحدات معالجة الرسومات.

البرمجة التعاونية باستخدام الذكاء الاصطناعي
وحدات GPU جاهزة للعمل
أفضل الأسعار

HyperAI Newsletters

اشترك في آخر تحديثاتنا
سنرسل لك أحدث التحديثات الأسبوعية إلى بريدك الإلكتروني في الساعة التاسعة من صباح كل يوم اثنين
مدعوم بواسطة MailChimp
(1,1)-تحرير الكластر قابل للحل في وقت متعدد الحدود | مستندات | HyperAI