| Title: |
Periodic Gossiping in Back-To-Back Trees |
| Authors: |
Roger Labahn; André Raspaud; Universit'e Bordeaux I |
| Contributors: |
The Pennsylvania State University CiteSeerX Archives |
| Source: |
ftp://ftp.math.uni-rostock.de/pub/members/labahn/bbt.ps.Z |
| Publication Year: |
1996 |
| Collection: |
CiteSeerX |
| Description: |
The d-ary back-to-back tree of height k, BBT k d , consists of two complete d-ary trees of height k the leaves of which are identified. For a proper coloring of the edges of BBT k d with c d + 1 colors, we consider periodic gossiping, i.e. full-duplex all-to-all broadcasting in the 1-port model where communication is made on a link of color i at any time (round) j i mod c. We present a coloring for which this process finishes within k periods, where a period is the collection of c consecutive rounds. We prove that this is optimal for c = d + 1. Supported by the Universit'e Bordeaux I while this author visited the LaBRI. y Supported by the Op'eration RUMEUR of the French GDR C 3 1. Introduction We repeat the following ideas and notations from [7]: A proper coloring of the edges of a graph is an assignment of one color to each edge such that no vertex is incident to two edges of the same color. For a given simple and connected graph G = (V; E) and a proper coloring ' of the. |
| Document Type: |
text |
| File Description: |
application/postscript |
| Language: |
English |
| Relation: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1435 |
| Availability: |
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.1435 |
| Rights: |
Metadata may be used without restrictions as long as the oai identifier remains attached to it. |
| Accession Number: |
edsbas.D2611D7B |
| Database: |
BASE |