مشكلة المسار الأوسع

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

في هذا الرسم البياني، يبلغ عرض النطاق الترددي لأوسع مسار من مالدون إلى فيرينج 29، ويمر عبر كلاكتون، وتيبتري، وهارويتش، وبلاكسهول.

في خوارزميات الرسوم البيانية ، تُعرف مشكلة المسار الأوسع بأنها إيجاد مسار بين رأسين محددين في رسم بياني مُثقَّل ، مع تعظيم وزن الحافة ذات الوزن الأدنى في هذا المسار. تُعرف هذه المشكلة أيضًا بمشكلة المسار ذي السعة القصوى . من الممكن تكييف معظم خوارزميات أقصر مسار لحساب المسارات الأوسع، وذلك بتعديلها لاستخدام مسافة الاختناق بدلًا من طول المسار. [ 1 ] مع ذلك، في كثير من الحالات، توجد خوارزميات أسرع.

على سبيل المثال، في رسم بياني يُمثل الاتصالات بين أجهزة التوجيه في الإنترنت ، حيث يُمثل وزن الحافة عرض النطاق الترددي للاتصال بين جهازَي توجيه، فإن مشكلة أوسع مسار هي مشكلة إيجاد مسار من طرف إلى طرف بين عقدتين على الإنترنت يتمتع بأقصى عرض نطاق ترددي ممكن. [ 2 ] يُعرف أصغر وزن للحافة على هذا المسار بسعة المسار أو عرض نطاقه الترددي. بالإضافة إلى تطبيقاتها في توجيه الشبكات، تُعد مشكلة أوسع مسار أيضًا عنصرًا مهمًا في طريقة شولتز لتحديد الفائز في انتخابات متعددة الأطراف، [ 3 ] وقد طُبقت في التركيب الرقمي ، [ 4 ] وتحليل المسارات الأيضية ، [ 5 ] وحساب التدفقات القصوى . [ 6 ]

تُطرح مشكلة وثيقة الصلة، وهي مشكلة المسار الأدنى الأقصى أو مشكلة أقصر مسار ذي عنق زجاجة، والتي تُعنى بإيجاد المسار الذي يُقلل الوزن الأقصى لأي من حوافه. ولها تطبيقات تشمل تخطيط النقل . [ 7 ] يمكن تحويل أي خوارزمية لمشكلة المسار الأوسع إلى خوارزمية لمشكلة المسار الأدنى الأقصى، أو العكس، عن طريق عكس اتجاه جميع مقارنات الأوزان التي تُجريها الخوارزمية، أو بشكل مكافئ عن طريق استبدال وزن كل حافة بنفيه.

الرسوم البيانية غير الموجهة

في الرسم البياني غير الموجه ، يمكن إيجاد أوسع مسار على أنه المسار بين رأسين في الشجرة الممتدة القصوى للرسم البياني، ويمكن إيجاد مسار مينيمكس على أنه المسار بين رأسين في الشجرة الممتدة الدنيا. [ 8 ] [ 9 ] [ 10 ] ويترتب على هذا التكافؤ مباشرةً أن جميع أزواج المسارات الأوسع فين{\displaystyle n}يمكن حساب الرسم البياني غير الموجه ذي الرؤوس في وقتيا(ن2){\displaystyle O(n^{2})}[ 11 ]​

في أي رسم بياني، سواء كان موجهًا أو غير موجه، توجد خوارزمية مباشرة لإيجاد أوسع مسار بمجرد معرفة وزن الحافة ذات الوزن الأدنى: ببساطة، احذف جميع الحواف الأصغر وابحث عن أي مسار بين الحواف المتبقية باستخدام البحث بالعرض أولًا أو البحث بالعمق أولًا . بناءً على هذا الاختبار، توجد أيضًا خوارزمية خطية لإيجاد أوسع مسار بين s و t في رسم بياني غير موجه، لا تستخدم شجرة الامتداد القصوى. الفكرة الرئيسية للخوارزمية هي تطبيق خوارزمية إيجاد المسار الخطية على متوسط ​​وزن الحافة في الرسم البياني، ثم إما حذف جميع الحواف الأصغر أو تقليص جميع الحواف الأكبر وفقًا لوجود مسار من عدمه، ثم تكرار العملية في الرسم البياني الأصغر الناتج. [ 9 ] [ 12 ] [ 13 ]

استخدم فرنانديز، غارفينكل، وأربيول (1998) أقصر المسارات غير الموجهة ذات الاختناقات لتكوين صور جوية مركبة تجمع صورًا متعددة لمناطق متداخلة. في المسألة الفرعية التي ينطبق عليها حل مشكلة أوسع مسار، تم تحويل صورتين مسبقًا إلى نظام إحداثيات مشترك ؛ وتتمثل المهمة المتبقية في اختيار خط فاصل ، وهو منحنى يمر عبر منطقة التداخل ويفصل إحدى الصورتين عن الأخرى. تُنسخ وحدات البكسل على أحد جانبي الخط الفاصل من إحدى الصورتين، بينما تُنسخ وحدات البكسل على الجانب الآخر من الصورة الأخرى. على عكس طرق التركيب الأخرى التي تعتمد على متوسط ​​وحدات البكسل من كلتا الصورتين، ينتج عن هذه الطريقة صورة فوتوغرافية صالحة لكل جزء من المنطقة المصورة. يتم ترجيح حواف الرسم البياني الشبكي بتقدير عددي لمدى وضوح الخط الفاصل بصريًا عبر تلك الحافة، ثم يتم إيجاد أقصر مسار ذي اختناق بناءً على هذه الأوزان. إن استخدام هذا المسار كخط فاصل، بدلاً من أقصر مسار تقليدي، يجعل النظام يجد خطاً فاصلاً يصعب تمييزه في جميع نقاطه، بدلاً من السماح له بالموازنة بين وضوح أكبر في جزء من الصورة ووضوح أقل في أجزاء أخرى. [ 4 ]

يمكن استخدام حل مسألة المسار الأمثل بين زاويتين متقابلتين في رسم بياني شبكي لإيجاد مسافة فريشيه الضعيفة بين سلسلتين مضلعتين . هنا، يمثل كل رأس في الرسم البياني الشبكي زوجًا من القطع المستقيمة، واحدة من كل سلسلة، ويمثل وزن الحافة مسافة فريشيه اللازمة للانتقال من زوج من القطع إلى آخر. [ 14 ]

إذا كانت جميع أوزان حواف الرسم البياني غير الموجه موجبة ، فإن مسافات المينيماكس بين أزواج النقاط (أقصى أوزان حواف مسارات المينيماكس) تُشكل فضاءً فائق القياس ؛ وعلى العكس، فإن كل فضاء فائق القياس محدود ينشأ من مسافات المينيماكس بهذه الطريقة. [ 15 ] تسمح بنية البيانات المُنشأة من الشجرة الممتدة الدنيا بالاستعلام عن مسافة المينيماكس بين أي زوج من الرؤوس في وقت ثابت لكل استعلام، باستخدام استعلامات السلف المشترك الأدنى في شجرة ديكارتية . يُمثل جذر الشجرة الديكارتية أثقل حافة في الشجرة الممتدة الدنيا، وأبناء الجذر هم أشجار ديكارتية تُنشأ بشكل متكرر من الأشجار الفرعية للشجرة الممتدة الدنيا المُشكلة بإزالة أثقل حافة. ​​تُمثل أوراق الشجرة الديكارتية رؤوس الرسم البياني المُدخل، وتساوي مسافة المينيماكس بين رأسين وزن عقدة الشجرة الديكارتية التي تُمثل سلفهما المشترك الأدنى. بمجرد فرز حواف الشجرة الممتدة الدنيا، يمكن إنشاء هذه الشجرة الديكارتية في وقت خطي. [ 16 ]

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

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

جميع الأزواج

تُستخدم مسألة إيجاد أوسع مسار بين جميع أزواج المرشحين في طريقة شولتز لاختيار الفائز في الانتخابات متعددة الأطراف ، حيث يُرتب الناخبون المرشحين حسب تفضيلهم . تقوم طريقة شولتز بإنشاء رسم بياني موجه كامل ، حيث تُمثل الرؤوس المرشحين، ويرتبط كل رأسين بحافة. ​​تُوجه كل حافة من الفائز إلى الخاسر في منافسة ثنائية بين المرشحين اللذين تربطهما، وتُسمى بهامش الفوز في تلك المنافسة. ثم تحسب الطريقة أوسع المسارات بين جميع أزواج الرؤوس، والفائز هو المرشح الذي يمتلك رأسُه مسارات أوسع إلى كل منافس منه مقارنةً بالعكس. [ 3 ] تتوافق نتائج الانتخابات باستخدام هذه الطريقة مع طريقة كوندورسيه - حيث يفوز المرشح الذي يربح جميع المنافسات الثنائية تلقائيًا بالانتخابات بأكملها - ولكنها تسمح عمومًا باختيار فائز، حتى في الحالات التي تفشل فيها طريقة كوندورسيه نفسها. [ 17 ] وقد استخدمت العديد من المنظمات طريقة شولتز، بما في ذلك مؤسسة ويكيميديا . [ 18 ]

لحساب أعرض المسارات لجميع أزواج العقد في رسم بياني موجه كثيف ، كما هو الحال في تطبيقات التصويت، فإن أسرع طريقة معروفة من الناحية التقاربية تستغرق زمنًا قدره O ( n (3+ω)/2 ) ، حيث ω هو أسّ ضرب المصفوفات السريع . وباستخدام أفضل الخوارزميات المعروفة لضرب المصفوفات، يصبح هذا الحد الزمني O ( n²⁶⁸ ) . [ 19 ] في المقابل، يستخدم التطبيق المرجعي لطريقة شولز نسخةً معدلةً من خوارزمية فلويد-وارشال الأبسط ، والتي تستغرق زمنًا قدره O(n³) . [ 3 ] بالنسبة للرسوم البيانية المتفرقة ، قد يكون من الأجدى تطبيق خوارزمية المسار الأعرض من مصدر واحد بشكل متكرر .

مصدر واحد

إذا تم ترتيب الحواف حسب أوزانها، فإن نسخة معدلة من خوارزمية ديكسترا تستطيع حساب نقاط الاختناق بين رأس بداية محدد وكل رأس آخر في الرسم البياني، في زمن خطي. تكمن الفكرة الأساسية وراء تسريع هذه الخوارزمية مقارنةً بالنسخة التقليدية في أن تسلسل مسافات نقاط الاختناق لكل رأس، بالترتيب الذي تُعالج به هذه الخوارزمية الرؤوس، هو تسلسل فرعي رتيب من تسلسل أوزان الحواف المُرتّب؛ لذا، يمكن تنفيذ قائمة الانتظار ذات الأولوية في خوارزمية ديكسترا كقائمة انتظار دلو : وهي مصفوفة مُفهرسة بالأرقام من 1 إلى m (عدد الحواف في الرسم البياني)، حيث تحتوي الخلية i في المصفوفة على الرؤوس التي تكون مسافة نقطة الاختناق الخاصة بها مساوية لوزن الحافة التي تقع في الموضع i بالترتيب المُرتّب. تُمكّن هذه الطريقة من حل مشكلة أوسع مسار بنفس سرعة عملية الترتيب . على سبيل المثال، إذا تم تمثيل أوزان الحواف بأعداد صحيحة، فإن الحدود الزمنية لفرز قائمة من m عددًا صحيحًا ستنطبق أيضًا على هذه المشكلة. [ 13 ]

مصدر واحد ووجهة واحدة

يقترح بيرمان وهاندلر (1987) أن تستخدم مركبات الخدمة ومركبات الطوارئ مسارات مينيمكس عند عودتها من مهمة خدمة إلى قاعدتها. في هذا السياق، يُعدّ وقت العودة أقل أهمية من وقت الاستجابة في حال ورود طلب خدمة آخر أثناء عودة المركبة. باستخدام مسار مينيمكس، حيث يُمثّل وزن الحافة أقصى وقت سفر من نقطة على الحافة إلى أبعد نقطة ممكنة لطلب الخدمة، يُمكن تخطيط مسار يُقلّل من أقصى تأخير مُمكن بين تلقّي طلب الخدمة ووصول مركبة الاستجابة. [ 7 ] يستخدم الله ولي وحسون (2009) مسارات ماكسيمين لنمذجة سلاسل التفاعلات السائدة في الشبكات الأيضية ؛ في نموذجهم، يُمثّل وزن الحافة الطاقة الحرة للتفاعل الأيضي الذي تُمثّله الحافة. ​​[ 5 ]

يظهر تطبيق آخر لأوسع المسارات في خوارزمية فورد-فولكرسون لمسألة التدفق الأقصى . يؤدي التوسع المتكرر للتدفق على طول مسار ذي سعة قصوى في الشبكة المتبقية للتدفق إلى حد صغير، O ( m log U ) ، لعدد عمليات التوسع اللازمة لإيجاد التدفق الأقصى؛ هنا، يُفترض أن سعات الحواف أعداد صحيحة لا تتجاوز U. مع ذلك، لا يعتمد هذا التحليل على إيجاد مسار ذي سعة قصوى تمامًا؛ يكفي أي مسار تكون سعته ضمن عامل ثابت من السعة القصوى. يؤدي دمج فكرة التقريب هذه مع طريقة توسع أقصر مسار في خوارزمية إدموندز-كارب إلى خوارزمية للتدفق الأقصى بزمن تشغيل O ( mn log U ) . [ 6 ]

من الممكن إيجاد مسارات ذات سعة قصوى ومسارات ذات سعة دنيا قصوى بمصدر واحد ووجهة واحدة بكفاءة عالية حتى في نماذج الحساب التي تسمح فقط بمقارنة أوزان حواف الرسم البياني المدخل دون إجراء عمليات حسابية عليها. [ 13 ] [ 20 ] تحتفظ الخوارزمية بمجموعة S من الحواف المعروفة باحتوائها على حافة الاختناق في المسار الأمثل؛ في البداية، تكون S هي مجموعة جميع حواف الرسم البياني البالغ عددها m . في كل تكرار للخوارزمية، تُقسّم S إلى سلسلة مرتبة من المجموعات الفرعية S1 ، S2 ، ... ذات أحجام متساوية تقريبًا؛ يُختار عدد المجموعات الفرعية في هذا التقسيم بحيث يمكن إيجاد جميع نقاط التقسيم بين المجموعات الفرعية من خلال البحث المتكرر عن الوسيط في زمن O ( m ) . ثم تُعيد الخوارزمية ترجيح كل حافة من حواف الرسم البياني بفهرس المجموعة الفرعية التي تحتوي على الحافة، وتستخدم خوارزمية ديكسترا المُعدّلة على الرسم البياني المُعاد ترجيحه. استنادًا إلى نتائج هذه الحسابات، يمكن تحديد أي من المجموعات الفرعية تحتوي على وزن الحافة الحرجة في زمن خطي. ثم يتم استبدال المجموعة S بالمجموعة الفرعية Si التي تم تحديدها على أنها تحتوي على وزن الحافة الحرجة، ويبدأ التكرار التالي بهذه المجموعة الجديدة S. يزداد عدد المجموعات الفرعية التي يمكن تقسيم S إليها أُسّيًا مع كل خطوة، لذا فإن عدد التكرارات يتناسب مع دالة اللوغاريتم المتكرر ، O ( log * n ) ، ويكون الزمن الكلي O ( m log * n ) . [ 20 ] في نموذج حسابي حيث يكون وزن كل حافة عددًا صحيحًا، يمكن استبدال استخدام التنصيف المتكرر في هذه الخوارزمية بتقنية تقسيم القوائم لهان وثورب (2002) ، مما يسمح بتقسيم S إلى O ( √m ) مجموعة أصغر Si في خطوة واحدة ، ويؤدي إلى حد زمني إجمالي خطي. [ 21 ] 

مجموعات النقاط الإقليدية

يفصل الشريط الأزرق الداكن أزواج الأعداد الأولية الغاوسية التي يبلغ طول مسارها الأدنى الأقصى 2 أو أكثر.

تمّت دراسة صيغة معدّلة لمسألة المسار الأمثل الأدنى لمجموعات النقاط في المستوى الإقليدي . وكما هو الحال في مسألة الرسم البياني غير الموجّه، يمكن حلّ مسألة المسار الأمثل الأدنى الإقليدي بكفاءة من خلال إيجاد شجرة امتداد إقليدية دنيا : كل مسار في الشجرة هو مسار أمثل أدنى. مع ذلك، تصبح المسألة أكثر تعقيدًا عندما يُراد إيجاد مسار لا يُقلّل طول القفزة فحسب، بل يُقلّل أيضًا، بين المسارات ذات طول القفزة نفسه، الطول الإجمالي للمسار أو يُقاربه. يمكن تقريب الحلّ باستخدام مُوسّعات هندسية . [ 22 ]

في نظرية الأعداد ، تطرح مسألة الخندق الغاوسي غير المحلولة سؤالاً حول ما إذا كانت مسارات المينيماكس في الأعداد الأولية الغاوسية ذات طول مينيماكس محدود أم غير محدود. أي، هل يوجد ثابت B بحيث يكون طول حافة مسار المينيماكس بين p و q في الأعداد الأولية الغاوسية، لكل زوج من النقاط p و q في مجموعة النقاط الإقليدية اللانهائية المعرفة بالأعداد الأولية الغاوسية، لا يتجاوز B ؟ [ 23 ] 

مراجع

  1. ↑ بولاك، موريس (1960)، "السعة القصوى عبر الشبكة"، بحوث العمليات ، 8 (5): 733-736 ، doi : 10.1287/opre.8.5.733 ، JSTOR 167387 
  2. ↑ شاشام، ن. (1992)، "توجيه البث المتعدد للبيانات الهرمية"، المؤتمر الدولي للاتصالات (ICC '92) ، المجلد 3، الصفحات 1217-1221 ، doi : 10.1109/ICC.1992.268047 ، hdl : 2060/19990017646 ، ISBN   978-0-7803-0599-1، S2CID 60475077 وانغ ، تشنغ؛ كروكروفت، ج. (1995)، "خوارزميات التوجيه القائمة على عرض النطاق الترددي والتأخير"، المؤتمر العالمي للاتصالات السلكية واللاسلكية IEEE (GLOBECOM '95) ، المجلد 3، الصفحات 2129-2133 ، doi : 10.1109/GLOCOM.1995.502780 ، ISBN   978-0-7803-2509-8، S2CID 9117583 
  3. 1 2 3 شولز، ماركوس (2011)، "طريقة انتخابية جديدة أحادية الفائز، رتيبة، مستقلة عن الاستنساخ، متناظرة عكسيًا، ومتسقة مع كوندورسيه"، الاختيار الاجتماعي والرفاهية ، 36 (2): 267-303 ، doi : 10.1007/s00355-010-0475-4 ، S2CID 1927244 
  4. 1 2 فرنانديز، إيلينا ؛ غارفينكل، روبرت؛ أربيول، رومان (1998)، "فسيفساء الخرائط الفوتوغرافية الجوية عبر وصلات محددة بأقصر المسارات عند نقاط الاختناق"، بحوث العمليات ، 46 (3): 293-304 ، doi : 10.1287/opre.46.3.293 ، JSTOR 222823 
  5. 1 2 الله، إي.؛ لي، كيونغ بوم؛ حسون، س. (2009)، "خوارزمية لتحديد مسارات التمثيل الغذائي ذات الحافة المهيمنة"، المؤتمر الدولي IEEE/ACM للتصميم بمساعدة الحاسوب (ICCAD 2009) ، الصفحات 144-150 
  6. 1 2 أهوجا، رافيندرا ك .؛ ماجنانتي، توماس ل .؛ أورلين، جيمس ب. (1993)، "7.3 خوارزمية توسيع السعة"، تدفقات الشبكة: النظرية والخوارزميات والتطبيقات ، برنتيس هول، ص 210-212 ، ISBN  978-0-13-617549-0
  7. 1 2 بيرمان، أوديد؛ هاندلر، غابرييل واي. (1987)، "المسار الأمثل الأدنى الأقصى لوحدة خدمة واحدة على شبكة إلى وجهات غير خدمية"، علوم النقل ، 21 (2): 115-122 ، doi : 10.1287/trsc.21.2.115
  8. ↑ هو، تي سي (1961)، "مشكلة المسار ذي السعة القصوى"، بحوث العمليات ، 9 (6): 898-900 ، doi : 10.1287/opre.9.6.898 ، JSTOR 167055 
  9. 1 2 بونين، أبراهام ب. (1991)، "خوارزمية زمنية خطية لمسألة المسار ذي السعة القصوى"، المجلة الأوروبية لبحوث العمليات ، 53 (3): 402-404 ، doi : 10.1016/0377-2217(91)90073-5
  10. ↑ مالباني، نافنيت؛ تشين، جيانر (2002)، "ملاحظة حول الإنشاء العملي لمسارات النطاق الترددي الأقصى"، رسائل معالجة المعلومات ، 83 (3): 175-180 ، doi : 10.1016/S0020-0190(01)00323-4 ، MR 1904226 
  11. ↑ شابيرا، آصف؛ يوستر، رافائيل ؛ زويك، أوري (2011)، "مسارات الاختناق لجميع الأزواج في الرسوم البيانية الموزونة بالرؤوس"، Algorithmica ، 59 (4): 621-633 ، doi : 10.1007/s00453-009-9328-x ، MR 2771114 انظر البند 4.1، صفحة 630
  12. ↑ كاميريني، ب.م. (1978)، "مسألة الشجرة الممتدة الدنيا-القصوى وبعض التوسعات"، رسائل معالجة المعلومات ، 7 (1): 10-14 ، doi : 10.1016/0020-0190(78)90030-3
  13. 1 2 3 كايبل، فولكر؛ Peinhardt, Matthias AF (2006)، حول مشكلة أقصر مسار لعنق الزجاجة (PDF) ، تقرير ZIB 06-22، Konrad-Zuse-Zentrum für Informationstechnik Berlin
  14. ↑ Alt, Helmut ; Godau, Michael (1995), "حساب مسافة فريشيه بين منحنيين مضلعين" (ملف PDF) ، المجلة الدولية للهندسة الحسابية وتطبيقاتها ، 5 ( 1-2 ): 75-91 ، doi : 10.1142/S0218195995000064.
  15. ^ لوكلير، برونو (1981)، “Description combinatoire des Ultramétriques”، مركز الرياضيات الاجتماعية. المدرسة العملية للدراسات العليا. الرياضيات والعلوم الإنسانية (باللغة الفرنسية) (73): 5-37 ، 127، السيد 0623034 
  16. ↑ ديمين، إريك د .؛ لاندو، جاد م .؛ وايمان، أورين (2009)، "حول الأشجار الديكارتية واستعلامات الحد الأدنى للنطاق"، الأوتوماتا واللغات والبرمجة، الندوة الدولية السادسة والثلاثون، ICALP 2009، رودس، اليونان، 5-12 يوليو 2009 ، سلسلة محاضرات في علوم الحاسوب، المجلد 5555، الصفحات 341-353 ، doi : 10.1007/978-3-642-02927-1_29 ، hdl : 1721.1/61963 ، ISBN   978-3-642-02926-4
  17. ↑ وبشكل أكثر تحديدًا، فإن النوع الوحيد من التعادل الذي تفشل طريقة شولتز في كسره هو بين مرشحين لديهما مسارات واسعة متساوية للوصول إلى بعضهما البعض.
  18. ↑ انظر جيسي بلاموندون-ويلارد، انتخابات مجلس الإدارة لاستخدام التصويت التفضيلي ، مايو 2008؛ مارك رايان، نتائج انتخابات مجلس إدارة ويكيميديا ​​لعام 2008 ، يونيو 2008؛ انتخابات مجلس الإدارة لعام 2008 ، يونيو 2008؛ وانتخابات مجلس الإدارة لعام 2009 ، أغسطس 2009.
  19. ↑ دوان، ران؛ بيتي، سيث ( 2009)، "خوارزميات سريعة لضرب المصفوفات (القصوى، الدنيا) وأقصر المسارات ذات الاختناق" ، وقائع الندوة السنوية العشرين لجمعية ACM-SIAM حول الخوارزميات المنفصلة (SODA '09) ، الصفحات 384-391 للاطلاع على خوارزمية سابقة استخدمت أيضًا ضرب المصفوفات السريع لتسريع مسارات جميع الأزواج الأوسع، انظر: Vassilevska, Virginia ; Williams, Ryan ; Yuster, Raphael (2007), "مسارات عنق الزجاجة لجميع الأزواج للرسوم البيانية العامة في وقت أقل من التكعيبي حقًا"، وقائع الندوة السنوية التاسعة والثلاثين لجمعية ACM حول نظرية الحوسبة (STOC '07) ، نيويورك: ACM، الصفحات 585-589 ، CiteSeerX 10.1.1.164.9808 ، doi : 10.1145/1250790.1250876 ، ISBN   9781595936318، MR 2402484 ، S2CID 9353065  والفصل الخامس من كتاب فاسيلفسكا، فيرجينيا (2008)، خوارزميات فعالة لمشاكل المسار في الرسوم البيانية الموزونة (ملف PDF) ، أطروحة دكتوراه، التقرير CMU-CS-08-147، كلية علوم الحاسوب بجامعة كارنيجي ميلون
  20. 1 2 جابو، هارولد ن .؛ تارجان، روبرت إي. (1988)، "خوارزميات لمسائل تحسين عنق الزجاجة المزدوجة" ، مجلة الخوارزميات ، 9 (3): 411-417 ، doi : 10.1016/0196-6774(88)90031-4 ، MR 0955149 
  21. ↑ هان، ييجي؛ ثورب، م. (2002)، "فرز الأعداد الصحيحة في زمن متوقع O( n √ log log n ) ومساحة خطية"، وقائع الندوة السنوية الثالثة والأربعين حول أسس علوم الحاسوب (FOCS 2002) ، الصفحات 135-144 ، doi : 10.1109/SFCS.2002.1181890 ، ISBN  978-0-7695-1822-0، S2CID 5245628 .
  22. ↑ بوز، بروسنجيت ؛ ماهيشواري، أنيل؛ ناراسيمهان، جيري؛ سميد، ميشيل؛ زيه، نوربرت (2004)، "تقريب أقصر المسارات الهندسية ذات الاختناقات"، الهندسة الحسابية: النظرية والتطبيقات ، 29 (3): 233-249 ، doi : 10.1016/j.comgeo.2004.04.003 ، MR 2095376 
  23. ↑ جيثنر، إيلين؛ واجن، ستان ؛ ويك، برايان (1998)، "جولة في الأعداد الأولية الغاوسية"، المجلة الرياضية الأمريكية الشهرية ، 105 (4): 327-337 ، doi : 10.2307/2589708 ، JSTOR 2589708 ، MR 1614871  .