An O (kn log (Kn)) algorithm for the KTH best spanning tree in series parallel graphs
Author
Source
The Arabian Journal for Science and Engineering. D, Mathematics
Issue
Vol. 35, Issue 1D (31 May. 2010), pp.29-35, 7 p.
Publisher
King Fahd University of Petroleum and Minerals
Publication Date
2010-05-31
Country of Publication
Saudi Arabia
No. of Pages
7
Main Subjects
Abstract AR
ليكن (V,E) مخططا مع دالة وزن W على حوافه، و ليكن K عددا صحيحا موجبا مسالة أفضل شجرة توليد (KBST) (spanning trees) هي إيجاد K من أشجار التوليد Tk و Tu T2,٠٠٠ بحيث لا توجد شجرة توليد ذات ورو أقل (على التوالي اكبر) من أوزانها.
درجة صعوبة هذه المسالة هي NP.
سوف نحسن تعقيد وقت التشغيل ل KBST في المخططات ذات السلاسل المتوازية.
KBST لها تطبيقات في استمثال طرق شبكات الكمبيوتر.
Abstract 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.
American Psychological Association (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
Modern Language Association (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
American Medical Association (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
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references : p. 32-34
Record ID
BIM-546321
