On Single Source Reachability Improvement

الموضوعات

علوم تطبيقية وتكنولوجية

الملخص

The problem of augmenting a given network, or graph, via edge-additions for improved reachability from a given source node is considered. We formulate and study the following Single Source Reachability Improvement problem (SSRI): given a graph G = (II, E), with a special (source) vertex s and two nonnegative integers d and k, can the addition of at most k edges result in a graph in which every vertex is at distance at most d from the source vertex. We also study the partial variant of the problem, which requires that at least some percentage of the vertices be within a distance of d from the source vertex. To the best of our knowledge, this partial variant has not been studied previously.We investigate the computational complexity of our problem with respect to the number of edge additions and the desired distance-bound. We show the NP­ hardness and present an effective polynomial-time greedy algorithm. Experimental evaluation of our greedy algorithm is conducted on randomly generated graphs, using the Erdos-Renyi approach. Compared to previously known methods, our ap­proach exhibits constant increase in the effectiveness by using smaller number of edge addition operations to achieve total reachability. Finally, we study a new vari­ant of the problem, dubbed Bounded Capacity Reachability Improvement (BCRI). In this case, each vertex can have a given limited number of edges connected to it. Experimental results show that our greedy method, applied to BCRI instances, is highly effective on weekly connected graphs.

روابط وملفات

التعريف والنوع

رقم الوثيقة

0307f12f-ccc2-4909-8727-bdd2780b210d

رقم العقد

0

نوع الوسائط

Crawler

نوع المحتوى

الرسائل العلمية

صيغة المصدر

رسائل ماجيستير

نوع الملف

pdf text

أسماء الملفات

841735_1.pdf

بيانات النشر

ألقاب المؤلفين

[{"name_ar":" Faisal Abu Khzam ","title_ar":"اشراف","title_en":"Supervision"},{"name_ar":"Hashem Alkak","title_ar":"اعداد","title_en":"Preparation"}]

اللغة

English

المصدر والدورية

اسم المصدر

On Single Source Reachability Improvement

المحتوى والصفحات

عدد الصفحات

0

كلمات الباحثين

Network Reachability Single Source Reachability Improvement Single Source Total Reachability

إشراف وإعداد

الإشراف

Faisal Abu Khzam

الإعداد

Hashem Alkak

الاقتباسات الببليوغرافية