×

Periodic gossiping on trees. (English) Zbl 0836.68085

Summary: In periodic gossip schemes, the calls are periodically repeated according to a proper coloring of the edges of the underlying graph with integers \(1, 2, \dots, c\). One period consists of \(c\) consecutive rounds \(1, \dots, c\) each containing time-parallel bidirectional calls on all edges with the same color. The problem is to design colorings which minimize the number of periods until gossiping is completed. We present an algorithm yielding “reasonable” colorings for trees, and discuss cases where it produces an optimal coloring. For these cases, the periodic gossip time, i.e. the minimum number of periods can be computed from the algorithm.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C15 Coloring of graphs and hypergraphs
94C15 Applications of graph theory to circuits and networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Liestman, A. L.; Richards, D., Network communication in edge-colored graphs: gossiping, IEEE Trans. Parallel Distrib. Systems, 4, 438-445 (1993)
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.