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.

اخر الاخبار

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

الهيأة العليا وجمعية العميد تعقدان اجتماعا لمناقشة آليات التعاون العلمي المشترك

لتقديم الدعم النفسي والمعنوي قسم الشؤون الطبية يزور أطفال مرضى السرطان في مستشفى الإمام الحسن (عليه السلام)

قسم الشؤون الفكرية يهدي إصداراته الحديثة إلى مكاتب المراجع وعدد من المؤسسات في بابل

عبر مركز الكفيل للصحة والسلامة.. قسم الشؤون الطبية يستأنف ورش الإسعافات الأوّلية للمنتسبين

المزيد

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

سرّ بسيط لصحة القلب.. أطعمة تخفض الكوليسترول خلال أسابيع

سبب خفي لإعتام عدسة العين ؟

عوامل خفية تسرّع شيخوخة الدماغ

أسباب الرغبة الشديدة في تناول الحلويات والأطعمة النشوية

المزيد

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

كندا تصنع كاسحة جليد من جيل جديد

رواد "أرتيميس 2" يكشفون تفاصيل حياتهم في الفضاء

حفريات صينية تكشف كائنات بحرية عاشت قبل 546 مليون عام

روسيا تطلق صاروخ "سويوز-2.1 إيه" من قاعدة بليسيتسك الفضائية

المزيد

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

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