خوارزميات الحساب المحلي في الحالة المتوسطة

نبدأ دراسة خوارزميات الحساب المحلي على مدخلات الحالة المتوسطة. في نموذج خوارزمية الحساب المحلي (LCA)، نحصل على وصول استقصائي إلى رسم بياني ضخم، ومطلوب منا الإجابة عن استفسارات العضوية حول بعض الهياكل التبادلية على الرسم البياني، مع الإجابة على كل استفسار بعمل دون الخطي. على سبيل المثال، توفر LCA لمشكلة k-spanner وصولًا إلى فرع ضعيف H G يحافظ على المسافات حتى عامل k. نبني LCAs بسيطة لهذه المشكلة بافتراض أن الرسم البياني المدخل مأخوذ من نماذج رسم بياني إردوس-رايني ونموذج الارتباط التفضيلي المدروسة جيدًا. في كلا الحالتين، تحقق سباننا أحجامًا وامتدادات تجارية من المستحيل تحقيقها للرسم البياني العام، بينما تمتلك تعقيد استعلامات أقل بشكل ملحوظ من LCAs في أسوأ الحالات. تحقق النتيجة الثانية لدينا تقاطع LCA مع مولدات الوصول المحلي (LAGs). توفر مولدات الوصول المحلي وصولاً فعالاً للاستعلام إلى كائن عشوائي، على سبيل المثال رسم بياني عشوائي إردوس-رايني. نستكشف المشكلة الطبيعية لإنشاء رسم بياني عشوائي مع هيكل تبادلي عليه. نظهر أن هذه المجموعة يمكن أن تكون أسهل في الحل من التركيز على كل مشكلة بمفردها، من خلال بناء خوارزمية سريعة وبسيطة توفر وصولًا إلى رسم بياني عشوائي إردوس-رايني مع مجموعة مستقلة قصوى.