القطر (نظرية الرسم البياني)

يمكن حساب قطر الرسم البياني باستخدام خوارزمية أقصر مسار لحساب أقصر المسارات بين جميع أزواج الرؤوس، ثم اختيار أكبر مسافة من بين هذه المسافات. على سبيل المثال، في رسم بياني ذي أوزان حواف موجبة، يمكن القيام بذلك باستخدام خوارزمية ديكسترا بشكل متكرر ، مرة واحدة لكل رأس بداية محتمل.${\displaystyle n}$الرؤوس و${\displaystyle m}$الحواف، وهذا يستغرق وقتاً${\displaystyle O(mn+n^{2}\log n)}$يُعد حساب أقصر المسارات بين جميع الأزواج أسرع طريقة معروفة لحساب قطر الرسم البياني الموزون بدقة. ^{[ 4 ]}

في الرسم البياني غير الموزون، يمكن استبدال خوارزمية ديكسترا ببحث العرض أولاً ، مما يوفر الوقت${\displaystyle O(mn)}$أو بدلاً من ذلك، يمكن حساب القطر باستخدام خوارزمية تعتمد على ضرب المصفوفات السريع ، في وقت يتناسب مع وقت الضرب.${\displaystyle n\times n}$المصفوفات، تقريبًا${\displaystyle O(n^{2.37})}$باستخدام خوارزميات ضرب المصفوفات المعروفة. ^{[ 5 ]} بالنسبة للرسوم البيانية المتفرقة، ذات الحواف القليلة، يكون البحث بالعرض أولاً المتكرر أسرع من ضرب المصفوفات. بافتراض فرضية الزمن الأسي القوي ، فإن البحث بالعرض أولاً المتكرر يكون شبه مثالي: تشير هذه الفرضية إلى أنه لا توجد خوارزمية يمكنها تحقيق زمن${\displaystyle O(m^{2-\varepsilon })}$لأي${\displaystyle \varepsilon >0}$[ ^{4 ]​}

من الممكن تقريب قطر الرسم البياني الموزون بنسبة تقريب تبلغ 3/2، في وقت${\displaystyle {\tilde {O}}(\min(m^{3/2},mn^{2/3})}$، حيث${\displaystyle {\tilde {O}}}$تُخفي هذه الصيغة عوامل لوغاريتمية في الحد الزمني. ^{[ 6 ]} في ظل فرضية الزمن الأسي القوي، لا يمكن إيجاد تقريب أكثر دقة أو أسرع بشكل ملحوظ من أقصر المسارات بين جميع الأزواج. ^{[ 4 ]}

يمكن حساب القطر في زمن خطي للرسوم البيانية الفاصلية ، ^{[ 7 ]} وفي زمن شبه خطي للرسوم البيانية ذات عرض الشجرة المحدود . ^{[ 8 ]} أما في الرسوم البيانية الوسيطة ، فيمكن إيجاد القطر في زمن شبه تربيعي.${\displaystyle {\tilde {O}}(n^{1.6456})}$[ ^{9 ]} في أي فئة من الرسوم البيانية المغلقة تحت ^قواطع الرسوم البيانية ، مثل الرسوم البيانية المستوية ، من الممكن حساب القطر في وقت أقل من تربيعي، مع أس يعتمد على عائلة الرسم البياني. ^{[ 10 ]}