تقليل الطول العمودي في الرسوم البيانية ذات الأعمدة المرتبطة

المعلومات الأساسية

• معرّف الورقة: 2511.16812
• العنوان: تقليل الطول العمودي في الرسوم البيانية ذات الأعمدة المرتبطة
• المؤلفون: Steven van den Broek (جامعة TU Eindhoven)، Marc van Kreveld (جامعة Utrecht)، Wouter Meulemans (جامعة TU Eindhoven)، Arjen Simons (جامعة TU Eindhoven)
• التصنيف: cs.CG (الهندسة الحسابية)
• تاريخ النشر/المؤتمر: تم تقديمها إلى arXiv في 20 نوفمبر 2025، بدأ البحث في ورشة عمل AGA 2024
• رابط الورقة: https://arxiv.org/abs/2511.16812

الملخص

الرسوم البيانية ذات الأعمدة المرتبطة (Linked Bar Chart) هي نسخة محسّنة من الرسوم البيانية العمودية التقليدية، حيث يتم تقسيم كل عمود إلى عدة كتل (blocks)، وتُربط هذه الكتل ببعضها البعض بواسطة خطوط متعامدة تعبر الأعمدة الوسيطة. يؤثر ترتيب الكتل بشكل مباشر على قابلية قراءة الخطوط الرابطة. تدرس هذه الورقة مشكلة الخوارزمية المتعلقة بتقليل الطول العمودي للخطوط الرابطة مع الحفاظ على ترتيب الأعمدة ثابتاً. التحدي الرئيسي يكمن في "الروابط المعتمدة" (dependent links)، حيث لا يمكن تحسين طولها العمودي بشكل مستقل. تُظهر الدراسة أنه: إذا كانت الروابط المعتمدة تشكل بنية غابة، يمكن حل المشكلة في الوقت O(nm) (n عمود، m رابط)؛ إذا كانت الروابط المعتمدة بين الأعمدة غير المتجاورة تشكل غابة، يمكن الحل في الوقت O(n⁴m)؛ في الحالة العامة، المشكلة قابلة للحل بمعامل ثابت (FPT) تحت معامل الدرجة القصوى للأعمدة.

خلفية البحث والدافع

1. المشكلة المراد حلها

الرسوم البيانية العمودية التقليدية تستطيع فقط تمثيل بيانات فئة واحدة، لكن في العديد من السيناريوهات العملية، بعض القيم لا تنتمي حصراً إلى فئة واحدة، بل ترتبط بفئات متعددة. على سبيل المثال:

• الكميات المشتركة: حجم الاتصالات بين الحسابات يظهر في إحصائيات حسابين
• عدم اليقين الثنائي: الناخبون المترددون بين حزبين في استطلاعات الرأي؛ مساهمة مصانع الحدود في تلوث البلدين

2. أهمية المشكلة

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

3. قيود الطرق الموجودة

• الرسوم البيانية العمودية القياسية لا تستطيع تصور البيانات عبر الفئات مباشرة
• على الرغم من أن الرسوم البيانية ذات الأعمدة المرتبطة اقتُرحت مؤخراً 17، إلا أن مشكلة تحسين ترتيب تكديس الكتل لم تُدرس بعد
• مشاكل رسم الرسوم البيانية التقليدية (مثل تضمين الكتاب أحادي الصفحة) تأخذ في الاعتبار فقط ترتيب الرؤوس، وليس بُعد تكديس الكتل الجديد هذا

4. دافع البحث

تدرس هذه الورقة للمرة الأولى بشكل منهجي مشكلة الخوارزمية المتعلقة بتقليل الطول العمودي للخطوط الرابطة في الرسوم البيانية ذات الأعمدة المرتبطة، مما يوفر أساساً نظرياً وخوارزميات فعالة لهذه الطريقة التصور الجديدة.

المساهمات الأساسية

1. تشكيل المشكلة: تعريف لأول مرة لمشكلة التحسين المتعلقة بتقليل الطول العمودي للخطوط الرابطة في الرسوم البيانية ذات الأعمدة المرتبطة، مع إدخال نظام تصنيف "الروابط المستقلة" و"الروابط المعتمدة"
2. خوارزمية البنية الغابية: إثبات أنه عندما يشكل الرسم البياني الجزئي للروابط المعتمدة غابة، يمكن حل المشكلة في الوقت O(nm) من خلال البرمجة الديناميكية (النظرية 3)
3. خوارزمية الغابة غير المتجاورة: إثبات أنه عندما تشكل الروابط المعتمدة غير المتجاورة غابة، يمكن حل المشكلة في الوقت O(n⁴m) (النظرية 6)
4. خوارزمية FPT: إثبات أن المشكلة قابلة للحل بمعامل ثابت في الحالة العامة، مع معامل الدرجة القصوى للأعمدة Δ، بتعقيد زمني O(Δ^(3δ)·δ·n) (النظرية 8)
5. حدود التعقيد: إثبات أنه عندما يمكن للرؤوس أن تحتوي على كتل غير مرتبطة متعددة قابلة للترتيب بشكل تعسفي، المشكلة هي NP-صعبة بقوة (النظرية 12)

شرح الطريقة

تعريف المهمة

الإدخال: رسم بياني موزون G = (V, E, w)، حيث:

• V: تسلسل ثابت من n رأس v₁, ..., vₙ
• E ⊆ V²: m حافة
• w: V ∪ E → ℝ⁺: دالة الأوزان (وزن الرأس = قيمة الفئة الواحدة، وزن الحافة = قيمة عبر الفئات)

الإخراج: ترتيب تكديس الكتل داخل كل عمود، بحيث:

• الطول العمودي الكلي للخطوط الرابطة يكون أقل ما يمكن
• الخطوط الرابطة التي تشترك في نقاط نهاية لا تتقاطع

القيود:

• ترتيب الأعمدة الأفقي ثابت
• الكتل غير المرتبطة توضع في أسفل العمود
• يجب أن تعبر الروابط جميع الأعمدة الوسيطة

المفاهيم الأساسية

1. تصنيف أنواع الروابط

تصنف الورقة الروابط إلى فئتين رئيسيتين:

الروابط المستقلة (IL): يمكن تحسين الطول العمودي بشكل مستقل بوضع الكتل في هدف ثابت t، بتكلفة |t - y| + |t - y'|. ثلاث حالات:

1. عمود وسيط معين أعلى من أعلى موضع ممكن لأحد نقاط النهاية → الهدف هو ارتفاع أعلى عمود وسيط H
2. فترات المواضع الممكنة لنقاط النهاية لا تتقاطع داخلياً → الهدف هو أقل موضع في الفترة الأعلى
3. موضع نقطة نهاية معينة ثابت (يقابل تسلسل فارغ) → الهدف هو هذا الموضع الثابت

الروابط المعتمدة (DL): الطول العمودي يعتمد على الموضع النسبي لكتلتين، لا يمكن تعيين هدف ثابت. تُقسم إلى:

• الروابط المعتمدة المتجاورة (ADL): تربط أعمدة متجاورة
• الروابط المعتمدة غير المتجاورة (NADL): تربط أعمدة غير متجاورة

اللمة الأساسية 1: الرسم البياني الجزئي للروابط المعتمدة هو رسم بياني خارج مستوي (outerplanar)، وبالتالي عرض الشجرة ≤ 2.

2. تمثيل الموضع وحساب التكلفة

بالنسبة للكتلة b في العمود Bⱼ (المقابلة للحافة اليسرى lᵢ ∈ Lⱼ)، إحداثيها العمودي المركزي هو:

y(b, k) = ½h(b) + w(vⱼ) + Σ(x=1 to i-1)h(lₓ) + Σ(x=1 to k)h(rₓ)

حيث k يمثل عدد الكتل اليمنى أسفلها.

دالة التكلفة:

• كتلة مستقلة b في الموضع i: λ(b, i) = |t - y(b, i)|
• رابط معتمد e في الموضع (i,j):

  λ(e, i, j) = {
    |H - y(b,i)| + |H - y(b',j)|  إذا كانت كلا نقاط النهاية أقل من H
    |y(b,i) - y(b',j)|            وإلا
  }
  

تصميم الخوارزمية

الخوارزمية 1: الروابط المعتمدة تشكل غابة (الوقت O(nm))

الفكرة الأساسية: استخدام بنية الشجرة لتحديد ترتيب معالجة الأعمدة، حساب البرمجة الديناميكية من الأسفل إلى الأعلى.

خطوات الخوارزمية:

1. اختر جذر تعسفي لكل شجرة T في الغابة
2. لكل عمود B، اجعل lₚ* الكتلة المرتبطة بالعقدة الأب (رابط الأب)
3. عرّف جدول البرمجة الديناميكية:
   • P(B, k): الحد الأدنى من التكلفة للشجرة الجزئية Tᵦ، مع وجود k كتل يمنى أسفل رابط الأب
   • D↓(p, q): الحد الأدنى من التكلفة للكتل p الأولى اليسرى و q الأولى اليمنى
   • D↑(p, q): الحد الأدنى من التكلفة للكتل اللاحقة
4. استراتيجية التحليل: كتلة رابط الأب lₚ* في الموضع k تقسم العمود إلى جزأين مستقلين:

   P(B, k) = D↓(p*-1, k) + D↑(p*+1, k+1)
   

5. الحساب التكراري لـ D↓:

   D↓(p, q) = min{
     D↓(p-1, q) + cost(lₚ, q),
     D↓(p, q-1) + cost(rᵧ, p)
   }
   

   
   بالنسبة للكتل المعتمدة، التكلفة هي: minⱼ λ(e, i, j) + P(B', j)

تحليل التعقيد الزمني:

• عند درجة كل عمود d، حساب جدول D يتطلب O(d²)
• حساب تكلفة الكتل المعتمدة مسبقاً: O(d·d')
• الوقت الإجمالي: O(Σd² + Σd·d') = O(nm)

الخوارزمية 2: الروابط المعتمدة غير المتجاورة تشكل غابة (الوقت O(n⁴m))

تحدي التوسع: السماح بالروابط المعتمدة المتجاورة (ADL)، يتطلب التعامل مع علاقات تبعية أكثر تعقيداً.

التقنيات الأساسية:

1. توسيع الغابة F: تضمين جميع NADL والحد الأقصى من مجموعة ADL (بدون تشكيل دورات)
2. تمثيل الحالة المحسّن: P*(B, k, l, r)، معاملات ثلاثة روابط معتمدة محتملة أحادية النقطة
3. معالجة ADL:
   • اجعل a←,1, a←,2, ... روابط ADL اليسرى، a→,1, a→,2, ... روابط ADL اليمنى
   • جداول البرمجة الديناميكية D↓(p, q, x, y) و D↑(p, q, x, y) تتطلب تتبع مواضع ADL

صيغة التكرار (عندما تكون lₚ كتلة معتمدة):

D↓(p, q, x, y) = min over χ of [
  min over x'(D↓(p-1, q, x', y) + λ(a←,i, χ, x')) +
  min over k'(P(B', k', x, χ) + λ(lₚ, k', q))
]

التعقيد الزمني:

• لكل زوج (p,q): O(Δ³) حساب مسبق + O(Δ³) حساب D
• إجمالي O(d²) زوج، O(Δ³d²) لكل عمود
• حساب P: O(Δ⁴d)
• الوقت الإجمالي: O(n⁴m)

الخوارزمية 3: خوارزمية FPT للحالة العامة (الوقت O(Δ^(3δ)·δ·n))

التقنية الأساسية: تحليل الشجرة (Tree Decomposition)

إطار الخوارزمية:

1. بناء تحليل شجرة nice للرسم البياني الجزئي للروابط المعتمدة G' (T, X, r)
   • عرض الشجرة ≤ 2 (خاصية الرسم البياني الخارج مستوي)
   • O(n) عقدة، كل حقيبة تحتوي على 3 أعمدة على الأكثر
   • يمكن بناؤها في الوقت O(n)
2. عرّف الحالة: P*(u, S₁, S₂, S₃)
   • u: عقدة في تحليل الشجرة
   • Sᵢ: حالة العمود Bᵢ في الحقيبة (موضع كل رابط معتمد)
   • تمثل الحد الأدنى من التكلفة لجميع الكتل والروابط في "الماضي" (past) من u
3. عدد الحالات (اللمة 9):
   • كل عمود: O(Δ^δ) حالة (دوال حقن من δ رابط معتمد إلى Δ موضع)
   • كل عقدة: O(Δ^(3δ)) حالة
4. المعالجة حسب نوع العقدة:
   • عقدة ورقية: P*(u) = 0، الوقت O(1)
   • عقدة الربط: P*(u, ...) = P*(v, ...) + P*(w, ...)، الوقت O(Δ^(3δ)·δ)
   • عقدة الإدخال: وراثة مباشرة من العقدة الفرعية، الوقت O(Δ^(3δ)·δ)
   • عقدة النسيان: الأكثر تعقيداً، تتطلب معالجة الكتل المستقلة والروابط المعتمدة للعمود المنسي
5. معالجة عقدة النسيان (اللمة 11):

   P*(u, S₁, S₂) = min over S∈Sf [
     P*(v, S₁, S₂, S) + IL(S) + DL(S, S₁) + DL(S, S₂)
   ]
   

   • حساب Dᵢ,ⱼ(p, q) مسبقاً: الحد الأدنى من التكلفة لمجموعة فرعية من الكتل المستقلة، الوقت O(Δ³)
   • كل حالة: الوقت O(Δ^δ·δ)
   • الإجمالي: الوقت O(Δ^(3δ)·δ)

التعقيد الزمني: O(n) عقدة × O(Δ^(3δ)·δ) = O(Δ^(3δ)·δ·n)

النتيجة الطبيعية:

• عندما Δ = O(1)، الخوارزمية بوقت متعدد الحدود
• عندما فقط δ = O(1) (درجة الروابط المعتمدة محدودة)، الخوارزمية لا تزال بوقت متعدد الحدود O(n)

نقاط الابتكار التقني

1. نظام تصنيف الروابط: تصنيف الروابط المستقلة/المعتمدة يسمح بتحليل مشكلة التحسين، الروابط المستقلة يمكن تحسينها محلياً، الروابط المعتمدة تتطلب اعتباراً عاماً
2. البرمجة الديناميكية الهرمية:
   • الخوارزمية 1: استخدام بنية الشجرة للتحليل
   • الخوارزمية 2: إدخال حالات معاملة للتعامل مع ADL
   • الخوارزمية 3: استخدام تحليل الشجرة للحالة العامة
3. استخدام خاصية الرسم البياني الخارج مستوي: خاصية الرسم البياني الجزئي للروابط المعتمدة الخارج مستوي تضمن عرض شجرة ≤ 2، مما يوفر أساساً نظرياً لخوارزمية FPT
4. استراتيجية الحساب المسبق: حساب تكلفة مجموعات فرعية من الكتل المستقلة مسبقاً في عقد النسيان، تجنب الحسابات المتكررة

إعداد التجارب

ملاحظة: هذه الورقة هي ورقة خوارزمية نظرية، لا تتضمن جزء التحقق التجريبي. تركز الورقة على تصميم الخوارزمية وتحليل التعقيد.

إثبات التعقيد

تثبت الورقة صعوبة المشكلة من خلال الاختزال:

النظرية 12 (صعوبة NP بقوة): عندما يمكن للرؤوس أن تحتوي على كتل غير مرتبطة متعددة قابلة للترتيب بشكل تعسفي، تقليل الطول العمودي للخطوط الرابطة هو NP-صعب بقوة.

طريقة الإثبات: اختزال من مشكلة 3-Partition

• البناء: 2k-1 عمود، B₀ يحتوي على n كتلة غير مرتبطة (يقابل مثيل 3-Partition)
• الخاصية الأساسية: فقط ترتيب الكتل غير المرتبطة في B₀ قابل للتعديل
• التكافؤ: وجود مخطط بطول عمودي صفر ⟺ وجود حل 3-Partition

نتائج التجارب

هذه الورقة عمل نظرية بحتة، لا تحتوي على جزء نتائج التجارب. النتائج الرئيسية هي:

ملخص التعقيد الزمني للخوارزميات

الاكتشافات النظرية

1. الاعتماد على البنية: يعتمد تعقيد المشكلة بشدة على البنية الرسومية للروابط المعتمدة
2. معاملة الدرجة: في الحالة العامة، المشكلة قابلة للحل بمعامل ثابت، عندما تكون درجة الروابط المعتمدة محدودة، يكون الوقت متعدد الحدود
3. بنية ارتفاع الأعمدة:
   • قيمة محلية قصوى واحدة → الروابط المعتمدة تشكل مجموعة مسارات
   • قيمة محلية دنيا واحدة → الروابط المعتمدة غير المتجاورة تشكل غابة

الأعمال ذات الصلة

1. مجال رسم الرسوم البيانية

• تضمين الكتاب أحادي الصفحة: الرسوم البيانية الخارج مستوي هي بالضبط التي يمكن رسمها بدون تقاطعات 1
• أهداف التحسين التقليدية:
  • تقليل عدد التقاطعات 5,13,14
  • تقليل طول الحافة 15,16
  • تقليل عدد الانحناءات 2,10,13,15
• مساهمة هذه الورقة: أول من يأخذ في الاعتبار بُعد ترتيب تكديس الكتل الجديد هذا

2. مقاييس جودة التصور

• تصور خطوط القصة: تأخذ في الاعتبار المسافة العمودية 9
• الرسوم البيانية للإحداثيات المتوازية: مقاييس مساحة الشاشة 7
• توسيع هذه الورقة: تطبيق مقياس المسافة العمودية على الرسوم البيانية ذات الأعمدة المرتبطة

3. مشاكل تحسين الرسوم البيانية

• الرسوم البيانية الخارج مستوي: تقليل إجمالي/أقصى طول حافة، cutwidth، bandwidth قابلة للحل بوقت متعدد الحدود 11
• الرسوم البيانية العامة: هذه المشاكل هي NP-صعبة 12
• موضع هذه الورقة: بين متعدد الحدود و NP-صعب، من خلال تحليل التعقيد المعامل

4. الرسوم البيانية ذات الأعمدة المرتبطة

• الاقتراح الأصلي: van Beusekom وآخرون 17 لتصور عدم اليقين المعتمد والمستقل
• مساهمة هذه الورقة: أول من يدرس بشكل منهجي مشكلة التحسين الخوارزمية لها

الخلاصة والمناقشة

الاستنتاجات الرئيسية

1. التعقيد الهرمي: يتراوح تعقيد المشكلة من O(nm) (بنية غابية) إلى FPT (حالة عامة) إلى NP-صعب بقوة (نسخة موسعة)
2. خوارزميات عملية: بالنسبة للبيانات المنظمة الشائعة (مثل توزيع ارتفاع أحادي القمة/أحادي الوادي)، توجد خوارزميات متعددة الحدود فعالة
3. قابلية الحل بمعامل ثابت: في الحالة العامة، عندما تكون درجة الأعمدة محدودة، يمكن حل المشكلة بكفاءة

القيود

1. ترتيب أعمدة ثابت: تفترض الخوارزميات أن ترتيب الأعمدة محدد مسبقاً، لم تأخذ في الاعتبار التحسين المشترك
2. خاصية نظرية: التعقيد الدقيق للحالة العامة (P مقابل NP) لا يزال غير محدد
3. نقص التحقق التجريبي: لم يتم توفير تطبيق فعلي للخوارزميات وتقييم الأداء
4. متطلبات بنية المثيل: قد لا تكون خوارزمية FPT عملية على مثيلات عالية الدرجة

الاتجاهات المستقبلية

تحدد الورقة بوضوح الاتجاهات البحثية التالية:

1. تحديد التعقيد: تحديد ما إذا كانت الحالة العامة مع ترتيب أعمدة ثابت هي NP-صعبة
2. التحسين المشترك: تحسين ترتيب الأعمدة وترتيب تكديس الكتل في نفس الوقت
3. توسيع التصميم:
   • الروابط غير المتماثلة: ارتفاعات كتل مختلفة في النقاط النهائية
   • مقاييس أخرى: تقليل عدد الانحناءات وغيرها
   • الرسوم البيانية الموجهة والمتعددة: ترتيب وتجميع روابط متعددة
   • الرسوم البيانية الفائقة: روابط بين ثلاثة أعمدة أو أكثر
4. التطبيقات العملية: تقييم أداء الخوارزمية على مجموعات البيانات الحقيقية

التقييم المتعمق

المميزات

1. الصرامة النظرية:
   • تحليل تعقيد شامل (من متعدد الحدود إلى FPT إلى NP-صعب)
   • إثباتات رياضية صارمة وتحليل التعقيد الزمني
   • تشكيل مشكلة واضح
2. تصميم خوارزمية ماهر:
   • يوفر تصنيف الروابط المستقلة/المعتمدة تحليلاً فعالاً للمشكلة
   • تستخدم الخوارزميات الثلاث تقنيات مختلفة مثل بنية الغابة وتحليل الشجرة
   • تصميم البرمجة الديناميكية دقيق، يستفيد بالكامل من بنية المشكلة
3. اكتمال النتائج:
   • يغطي حالات خاصة متعددة والحالة العامة
   • يوفر حدود عليا (خوارزميات) وحدود دنيا (صعوبة NP)
   • يوفر تحليل التعقيد المعامل تحديداً دقيقاً للتعقيد
4. وضوح الكتابة:
   • تعريفات المفاهيم واضحة (مثل أنواع الروابط، الماضي، إلخ)
   • الرسوم التوضيحية تساعد على الفهم (الأشكال 3-8)
   • عرض الخوارزميات تدريجي ومتقدم

أوجه القصور

1. نقص التحقق العملي:
   • لا توجد تجارب على بيانات فعلية
   • الكفاءة الفعلية لخوارزمية FPT عند Δ كبير غير معروفة
   • نقص المقارنة مع الخوارزميات الاستكشافية
2. فراغ التعقيد في الحالة العامة:
   • ما إذا كانت الحالة العامة مع ترتيب أعمدة ثابت هي NP-صعبة لا تزال غير محددة
   • إثبات الاختزال يعتمد على افتراض كتل غير مرتبطة متعددة، مما يختلف عن المشكلة الأصلية
3. التعقيد الزمني مرتفع:
   • O(n⁴m) للخوارزمية 2 قد لا يكون عملياً للمثيلات الكبيرة
   • الاعتماد الأسي للخوارزمية 3 على Δ^(3δ) ينفجر عند درجة أعلى
4. نطاق المشكلة محدود:
   • يأخذ في الاعتبار فقط هدف الطول العمودي الواحد
   • لم يأخذ في الاعتبار تقليل التقاطعات ومؤشرات جودة أخرى مهمة
   • افتراض ترتيب أعمدة ثابت قوي نسبياً

التأثير

1. المساهمة النظرية:
   • دراسة رائدة لمشكلة الخوارزمية في الرسوم البيانية ذات الأعمدة المرتبطة
   • توفير اتجاه بحثي جديد لتحسين التصور
   • عرض تطبيق التعقيد المعامل في التصور
2. القيمة العملية:
   • توفير إرشادات نظرية للأنظمة العملية
   • يمكن تطبيق خوارزميات الحالات الخاصة مباشرة
   • توفير معايير لتصميم الخوارزميات الاستكشافية
3. قابلية إعادة الإنتاج:
   • وصف الخوارزمية مفصل
   • الاشتقاق الرياضي كامل
   • لكن ينقصه تطبيق الكود

السيناريوهات المناسبة

1. التطبيق المباشر:
   • البيانات التي يكون توزيع ارتفاع الأعمدة فيها أحادي القمة/أحادي الوادي (الخوارزميات 1، 2)
   • الرسوم البيانية المتفرقة بدرجة أعمدة صغيرة (الخوارزمية 3)
   • السيناريوهات التي تكون فيها بنية الروابط المعتمدة بسيطة
2. يتطلب توسيع:
   • الرسوم البيانية الكثيفة الكبيرة (تتطلب خوارزميات استكشافية)
   • السيناريوهات التي تتطلب تحسين ترتيب الأعمدة بشكل مشترك
   • التحسين متعدد الأهداف (الطول + التقاطعات + الانحناءات)
3. الإرشادات النظرية:
   • تصميم أنظمة التصور
   • معالجة البيانات المسبقة (مثل ترتيب الأعمدة لتشكيل بنية غابية)
   • تقييم معايير الخوارزميات التقريبية

المراجع (المراجع الرئيسية)

1 Bernhart & Kainen (1979): سمك الكتاب للرسم البياني - النظرية الأساسية لتضمين الكتاب أحادي الصفحة

6 Cygan وآخرون (2015): خوارزميات معاملة - الكتاب المرجعي القياسي لخوارزميات FPT

11 Frederickson & Hambrusch (1988): الترتيبات الخطية المستوية للرسوم البيانية الخارج مستوي - خوارزميات متعددة الحدود لتحسين الرسوم البيانية الخارج مستوي

17 van Beusekom وآخرون (2024): تصور أحجام المجموعات مع عدم اليقين المعتمد والمستقل - الاقتراح الأصلي للرسوم البيانية ذات الأعمدة المرتبطة

التقييم الشامل: هذه ورقة عالية الجودة في الهندسة الحسابية النظرية، تدرس بشكل منهجي مشكلة الخوارزمية في تحسين الرسوم البيانية ذات الأعمدة المرتبطة. الورقة صارمة نظرياً، وتصميم الخوارزمية ماهر، وتحليل التعقيد شامل. القيمة الرئيسية تكمن في بناء أساس نظري قوي لهذه طريقة التصور الجديدة. أوجه القصور هي نقص التحقق التجريبي واكتمال تحديد التعقيد في الحالة العامة. إذا تمكنت من دمج تقييم البيانات الفعلية وتصميم الخوارزميات الاستكشافية في المستقبل، فستزيد بشكل كبير من قيمتها العملية.