النسخ المتماثل المقيد بالقطع الأدنى لتقسيم الرسم البياني الفائق على طريقة k
| العنوان | النسخ المتماثل المقيد بالقطع الأدنى لتقسيم الرسم البياني الفائق على طريقة k |
|---|---|
| المؤلف | يازيجي، فولكان، أيكانات، سي. |
| تاريخ النشر: | 2014 |
| مكان النشر | - يبلغ |
| الموضوع | التحسين التوافقي، الرسوم البيانية، الاستدلال، التحسين، البرمجة، الأعداد الصحيحة |
| النوع | دورية |
| اللغة | الإنجليزية |
| رقمي | نعم |
| مخطوط | لا |
| المكتبة: | جامعة اوزيجين |
| معرف أصل المكتبة | 1526-5528 |
| رقم السجل | c1a12b34-0a70-4ccd-986e-07966fdaf729 |
| موقع المكتبة | علوم الكمبيوتر |
| التاريخ | 2014 |
| ملاحظات | نظرًا لقيود حقوق الطبع والنشر، فإن الوصول إلى النص الكامل لهذه المقالة متاح فقط عبر الاشتراك. |
| نص عينة | النسخ المتماثل هو تقنية مستخدمة على نطاق واسع في أنظمة استرجاع المعلومات وقواعد البيانات لتوفير التسامح مع الأخطاء وتقليل تكاليف الموازاة والمعالجة. تم اقتراح نماذج اندماجية تعتمد على تقسيم الرسم البياني الزائد لمختلف المشكلات الناشئة في أنظمة استرجاع المعلومات وقواعد البيانات. نحن ندرس إمكانية استخدام النسخ المتماثل الرأسي لتحسين جودة تقسيم الرسم البياني الزائد. في هذه الدراسة، نركز على مشكلة النسخ المتماثل المقيد (CMCR)، حيث تم منحنا في البداية أقصى سعة للنسخ المتماثل وقسم رسم بياني فائق K-way مع نسبة اختلال أولية. الهدف في مشكلة CMCR هو العثور على مجموعات النسخ المتماثل الرأسية المثالية لكل جزء من القسم المحدد بحيث يتم تقليل حجم القطع الأولي للقسم، حيث يتم الحفاظ على عدم التوازن الأولي أو تقليله تحت قيود سعة النسخ المتماثل المحددة. في هذه الدراسة، نقدم تحليلًا لتعقيد مشكلة CMCR ونقترح نموذجًا يعتمد على مزيج فريد من مخططات البرمجة الخطية الخشنة والأعداد الصحيحة (ILP). هذه الخوارزمية الخشنة مشتقة من استخدام جديد لتحلل دولماج-مندلسون. تظهر التجارب أن تركيبة ILP المقترنة بالخشونة القائمة على تحلل Dulmage-Mendelsohn توفر نتائج عالية الجودة في أوقات التنفيذ العملية لتقليل حجم القطع لقسم الرسم البياني الزائدي على شكل K. |
| DOI | 10.1287/ijoc.2013.0567 |
| Cilt | 26 |
