Broadcast Time

Consider a broadcast scheme on a connected graph from an originator vertex  in a graph  consisting of a sequence of parallel calls starting from . In each time step, every informed node (sender) can call at most one uninformed neighbor (receiver), corresponding to a directed edge. The process is iterated until every vertex in the network is informed, with the result being a directed spanning tree of  rooted at  called the broadcast tree of originator .

The minimum number of time steps required to broadcast from  to all vertices in the graph  is called the broadcast time of vertex , denoted . The maximum broadcast time over all originator vertices in  is called the broadcast time of , denoted  (Harutyunyan1 and Li 2019).

The broadcast time of a disconnected graph is the maximum of the broadcast times of its connected components.

---

REFERENCES

Farley, A. M. "Minimal Broadcast Networks." Networks 9, 313-332, 1979.

Harutyunyan, H. A. and Li, Z. "A Simple Construction of Broadcast Graphs." In Computing and Combinatorics. COCOON 2019 (Ed. D. Z.and C. Tian.) Cham, Switzerland: Springer, pp. 240-253, 2019.

Ivanova, M.; Haugland, D.; and Tvedt, B. H. "Computing the Broadcast Time of a Graph." 13 Jul 2021. https://arxiv.org/abs/2107.06359v1.

اخر الاخبار

اخبار العتبة العباسية المقدسة

قسم الشؤون الفكرية يطلق باقة من النشاطات الرقمية الخاصة بشهر المحرم

العتبة العباسية المقدسة تختتم السلسلة الأولى لمشروع المحاضرات القرآنية العاشورائية في بابل

العتبة العباسية المقدسة تسلّم راية العزاء إلى تجمّع مواكب محافظة الديوانية

قسم الشؤون الفكرية يواصل إقامة المجالس الحسينية ضمن سلسلة (بيوت النعيم)

المزيد

الآخبار الصحية

تناول الجبن.. مفيد للجسم أم خطر يهدد صحتك؟

طبيبة أسنان تحذر.. لا تتجاهل هذه العلامة بعد التنظيف

يجب أن تأكل المزيد من الشمام هذا الصيف.. إليك السبب ؟

تأثير صحي كبير.. كم بيضة يجب أن تتناول يوميا؟

المزيد

الآخبار التكنلوجية

أداء خلايا البيروفسكايت الشمسية تحت الماء قد يزيد كفاءة تحويل الكهرباء

مسافة الأمان: أساس القيادة الآمنة وتجنب الحوادث

هل القيادة السريعة تعني استهلاك اكثر للوقود؟

لماذا يعتبر كوكب المريخ غير صالح للحياة؟

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength