An O (kn log (Kn)) algorithm for the KTH best spanning tree in series parallel graphs
المؤلف
المصدر
The Arabian Journal for Science and Engineering. D, Mathematics
العدد
المجلد 35، العدد 1D (31 مايو/أيار 2010)، ص ص. 29-35، 7ص.
الناشر
جامعة الملك فهد للبترول و المعادن
تاريخ النشر
2010-05-31
دولة النشر
السعودية
عدد الصفحات
7
التخصصات الرئيسية
الملخص AR
ليكن (V,E) مخططا مع دالة وزن W على حوافه، و ليكن K عددا صحيحا موجبا مسالة أفضل شجرة توليد (KBST) (spanning trees) هي إيجاد K من أشجار التوليد Tk و Tu T2,٠٠٠ بحيث لا توجد شجرة توليد ذات ورو أقل (على التوالي اكبر) من أوزانها.
درجة صعوبة هذه المسالة هي NP.
سوف نحسن تعقيد وقت التشغيل ل KBST في المخططات ذات السلاسل المتوازية.
KBST لها تطبيقات في استمثال طرق شبكات الكمبيوتر.
الملخص EN
Given a graph G = (V, E) with a weight function w on its edges and a positive integer number K, the Kth best spanning tree (KBST) problem is to find K distinct spanning trees T1, T2, … ,TK such that there is no spanning tree with a weight less (respectively more) than their weights.
This problem is NP-hard.
We improve the running time complexity of KBST in series parallel graphs.
KBST has applications in computer network routing optimization.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Chaourar, Brahim. 2010. An O (kn log (Kn)) algorithm for the KTH best spanning tree in series parallel graphs. The Arabian Journal for Science and Engineering. D, Mathematics،Vol. 35, no. 1D, pp.29-35.
https://search.emarefa.net/detail/BIM-546321
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Chaourar, Brahim. An O (kn log (Kn)) algorithm for the KTH best spanning tree in series parallel graphs. The Arabian Journal for Science and Engineering. D, Mathematics Vol. 35, no. 1D (May. 2010), pp.29-35.
https://search.emarefa.net/detail/BIM-546321
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Chaourar, Brahim. An O (kn log (Kn)) algorithm for the KTH best spanning tree in series parallel graphs. The Arabian Journal for Science and Engineering. D, Mathematics. 2010. Vol. 35, no. 1D, pp.29-35.
https://search.emarefa.net/detail/BIM-546321
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references : p. 32-34
رقم السجل
BIM-546321
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر
