مقدر الزحام من الأسفل إلى الأعلى

نطور خوارزمية جديدة لبناء مقدر الزحام بجودة بولي لوغاريتمية على رسم بياني غير موجه ذي سعة في زمن شبه خطي تقريبًا. نهجنا هو أول بناء هرمي *من الأسفل إلى الأعلى*، على عكس النهج السابق *من الأعلى إلى الأسفل* بما في ذلك نهج راكي وشاه وتوبايغ (SODA 2014)، وهو البناء الآخر الوحيد الذي يحقق جودة بولي لوغاريتمية ويمكن تطبيقه في زمن شبه خطي (بنغ، SODA 2016). مشابهًا لراكي وشاه وتوبايغ، يتطلب بناءنا في كل مستوى هرمي استدعاءات لروتين فرعي تقديري لمعدل التدفق/القطع الأدنى. ومع ذلك، فإن الميزة الرئيسية لنهجنا من الأسفل إلى الأعلى هي أن هذه الاستدعاءات لمعدل التدفق يمكن تنفيذها مباشرة *دون استخدام الاستدعاء الذاتي*. بدقة أكثر، يمكن تحويل المستويات المحسوبة مسبقًا من الهرمية إلى *مقدر زحام زائف*، والذي يتحول بعد ذلك إلى خوارزمية معدل تدفق كافية للاستدعاءات الخاصة بمعدل التدفق المستخدمة في بناء المستوى الهيراركي التالي. نتيجة لذلك، نحصل على أول خوارزميات غير استدعائية لمقدر الزحام ومعدل التدفق التقديري التي تعمل في زمن شبه خطي، وهو تحسين مفاهيمي للخوازميات المذكورة التي تتناوب بشكل استدعائي بين المشكلتين.