×

Broadcasting in generalized chordal rings. (English) Zbl 1031.68012

Summary: Broadcasting is an information dissemination process in which a message originating at one node of a communication network (modeled as an undirected graph) is sent to all other nodes by means of calls involving two nodes at a time, with each node participating in at most one call at any time. We are interested in efficient broadcasting in a class of cubic graphs known as generalized chordal rings. These graphs have been found useful for having a small diameter \(D\), among graphs with a given number of vertices and maximum degree. We show that the minimum broadcast time in any generalized chordal ring is \(D\), \(D+ 1\), or \(D+ 2\). For the generalized chordal rings of diameter \(D\) which have the greatest (or greatest-known) number of nodes, we then evaluate exactly the minimum broadcast time. It turns out to be \(D+ 1\) when \(D\) is even and \(D+ 2\) when \(D\) is odd. For these purposes, we review the construction of these extremal generalized chodal rings. We also review the optimal broadcast schemes for infinite triangular grids, which we use to prove our bounds. Finally, we ask for the maximum number of nodes that can be informed by a broadcast in time \(t\) in any generalized chordal ring. We answer this completely for even \(t\) and almost completely for odd \(t\). We use a geometric approach, based on plane tessellations.

MSC:

68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arden, IEEE Trans Comput C-30 pp 291– (1981)
[2] Barrière, Networks 36 pp 180– (2000)
[3] Bermond, J Parall Distrib Comp 22 pp 2– (1995)
[4] Fraigniaud, Discr Appl Math C-53 pp 79– (1994)
[5] and Broadcasting in one orthant, submitted.
[6] Hell, Discr Appl Math 21 pp 101– (1988)
[7] Broadcasting, graph homomorphisms and chord intersections, Ph.D. Thesis, Rutgers University, New Brunswick, NJ, 1979.
[8] Ko, AMS Notices pp a196– (1979)
[9] Liestman, Int J Found Comp Sci 9 pp 57– (1998)
[10] and ? The optimization of chordal ring networks,? Communication technology, and (Editors), World Scientific, Singapore, 1987, ISBN 9971-50-349-9, pp. 295-299.
[11] Peck, Stud Appl Math 62 pp 69– (1980) · Zbl 0457.05063
[12] Broadcasting in mesh-connected computers, Proc 1982 Conf Information Sciences and Systems, Princeton University, 1982, pp. 85-90.
[13] Yebra, Ars Combin 20B pp 159– (1985)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.