F. Comellasa, P. Hellb aUniversitat Politècnica de Catalunya,
Dep. Matemàtica Aplicada IV Campus Nord, Edifici C3, 08034 Barcelona, Catalonia, Spain. comellas@mat.upc.es bSimon Fraser University, School of Computing Science Burnaby, BC, V5K 1S6, Canada pavol@cs.sfu.ca
Final Manuscript for NETWORKS (4rd revision, June 2003)
Abstract
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, amongst graphs with 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 chordal 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.
Keywords: Generalized chordal rings; networks; communication; broadcasting;
plane tessellations
One of the simplest topologies for interconnection networks is the ring,
in which each node is connected to two other nodes, making up a
bidirectional loop. The ring has many attractive properties such as
simplicity, extendability, and low degree. On the other hand, it
suffers from poor reliability (the network is disconnected by the failure
of one processor, or two links), and high diameter (some messages have
to travel along half the ring to reach their destination). A natural way
to solve these problems without increasing the degree too much is to add
to the ring just one link per node, i.e., making a cubic (3-regular) graph.
To maintain the simplicity of the network a nice symmetric construction
is desirable.
The generalized chordal rings defined below have been
found to be a useful construction of this kind. They are known to have
a small diameter, and good connectivity properties [1,3].
For instance, the diameter of the ring with n nodes is n/2,
while the diameter of a good generalized chordal ring is
of order Ön.
Let n be an even positive integer, and a,b,c three distinct odd
positive integers smaller than n. The generalized chordal ring
(GCR) CRn(a,b,c) has the vertex set V=V0ÈV1,
where V0={0,2,4,¼,n-2} and V1={1,3,5,¼,n-1}.
Each node i Î V0 is adjacent to the nodes i+a,i+b,i+c Î V1
(node addition is always modulo n). Equivalently, each node
j Î V1 is adjacent to the nodes j-a,j-b,j-c Î V0.
In Figure 1(a), we illustrate the construction; the generalized
chordal ring CR14(1,-1,9) is also known as the Heawood graph.
The following facts about generalized chordal rings are well known
[10,13]:
Each GCR is bipartite
Each GCR is vertex transitive
(for any two nodes i,j some automorphism takes i to j;
in other words, all nodes are similar)
If r is even, then the GCR's CRn(a,b,c) and CRn(a+r,b+r,c+r)
are isomorphic
Indeed, these facts are easily seen: For instance, clearly, V0, V1
is a bipartition of any GCR. Moreover, the families of automorphisms
i ® i+a, a = 2,4,...,n-2 (these automorphisms
all maintain the sets V0,V1), and i ® b- i,
b = 1,3,...,n-1 (these exchange the sets V0,V1), suffice to
take any node to any other node. Finally, if r is even, then the
permutation keeping V0 fixed and adding r to all nodes of V1
is an isomorphism taking CRn(a,b,c) to CRn(a+r,b+r,c+r).
It follows from the last fact that
we can always choose one of the parameters
a, b, c to be any prescribed value. By convention, we shall always take a=1.
A chordal ring is a GCR with a=-b=1. (Thus the graph CR14(1,-1,9)
given in Figure 1 is actually a chordal ring.) Chordal rings were introduced
in the seminal paper of Arden and Lee [1].
We observe that GCR's admit three canonical perfect matchings:
Let x be one of the parameters a, b, c; match each node i, with
i even, with the node i+x (or, equivalently, match each node j,
with j odd, with the node j-x.) Then this is a perfect matching,
i.e., each node is matched with a unique other node.
Indeed, this is due to the simple observation that adding the odd integer x
defines a bijection between V0 and V1.
Figure 1: (a) The graph CR14(1,-1,9), known as the Heawood graph.
(b) A broadcast scheme in the Heawood graph.
The diameter of GCR's has been investigated in [1,10,13]. The first paper [1] claimed that the
maximum number of nodes a GCR of diameter D can have is D2 + O(D).
The latter two papers corrected this bound to [ 3/2]D2 + O(D),
and proved this to be asymptotically optimal. (This is further discussed
below.) The last paper [10] discussed also the harder problem
of constructing a GCR with the minimum diameter when the number of nodes
is given. These papers used a geometric technique of plane tessellations,
which we shall review below.
In this paper, we initiate a study of the broadcasting properties of GCR's.
Broadcasting is an information dissemination process in which a message
originating at one node (the originator of the broadcast)
of an undirected graph is to be transferred to all
other nodes, subject to the following rules [4]:
The transfer of the message from one node to another (termed a call)
takes one unit of time
A node can only call an adjacent node
A node can participate in at most one call per unit of time
A broadcast scheme is a description of the process of broadcasting.
Figure 1(b) illustrates a broadcast scheme in CR14(1,-1,9). Since all
nodes are similar, the originator can be chosen to be any node - we
chose the node 0. The heavy edges illustrate how, and when, the message
was transferred along the links. This scheme informs all nodes of the
graph CR14(1,-1,9) in five time units; it is known that no
broadcast scheme can inform all nodes in four time units (thus the
scheme is optimal).
The standard way to treat generalized chordal rings involves the use
of plane tessellations [2,13].
We associate with each CRn(a,b,c) a
labeling of the cells of the standard triangular grid.
One cell v0 of the triangular grid is chosen to hold the node 0
of our GCR. By convention, we choose the cell v0 to be a triangle
pointing `up'. Then, once a triangle pointing up has been labeled i,
we label its three neighbours (all are triangles pointing down) by
i+a, i+b, i+c, so that adding a always leads to the right, adding
b to the left, and adding c down. Similarly, once a triangle
pointing down has been labeled j, we label its neighbours (all
pointing up) by j-a, j-b, j-c, so that subtracting a leads
to the left, subtracting b to the right, and subtracting c up.
In this way, each GCR yields an associated labeling of the
triangular grid. It is important to note that the GCR is a finite
graph while the triangular grid is infinite. In fact, each node
of the GCR will appear in infinitely many cells. Which cells have
the same label depends on the arithmetic relations among the
parameters n, a, b, c.
It is easily seen [2,10] that taking
one cell of each kind of label
forms a `shape' which can be used to tile the entire plane. We shall
always choose the cell v0 as the cell labeled 0, and for any
other label, we shall choose a cell as near to v0 as possible.
One way to do this for the graph CR14(1,-1,9) is illustrated
in Figure 3(a). (It can also be shown, cf. [10,13],
that if a tile tessellates the plane, it corresponds to some CRn(a,b,c).)
We denote by Bi the ball of radius i, i.e., the set of
all cells of distance at most i from v0. Figure 4(c) illustrates
the balls Bi with even i=0,2,4,6; Figure 6(a) illustrates the
balls Bj with odd j=1,3,5,7.
We remark that our way of choosing the tiles implies the following
fact:
Proposition 1
Let G be a GCR of diameter D, and let T be a tile for G,
chosen according to the above rule. Then T is a subset of BD.
[¯]Our technique for defining a broadcast scheme in a GCR consists of
specializing a broadcast scheme for (a portion of) the triangular
grid to a suitable tile, and then interpreting it as a broadcast
scheme of the corresponding GCR. It will turn out that taking a
fastest possible broadcast scheme in the grid, together with the
`right' tile, will yield optimal broadcast schemes in the GCR.
For instance, Figure 3(b) illustrates
a broadcast scheme of seven time units which informs a part of
the triangular grid. All nodes corresponding to a tile arising
from the Heawood graph have been informed by time five. In fact,
this yields the (optimal) broadcast scheme given in Figure 1(b).
Figure 3: (a) A tessellation of the plane corresponding to
the Heawood graph. (b) A broadcast scheme in the triangular grid
(the italicized labels show when the cells are reached, the short
lines indicate calls made).
It follows that it is going to be useful to know how fast one can
broadcast in the triangular grid. This problem was considered and
solved by Ko [7,8]. Ko gave a broadcast scheme for the
triangular grid, and proved that for any fixed time t it reaches
the maximum possible number of nodes. In the next section, we shall
review the proof of this nice result, since it is not published in
full in an easily accessible source [7,8]. Using this
result we then prove that the optimal broadcast time in a chordal
ring of diameter D is D, D+1, or D+2.
In Section 5 we consider the problem of finding the
`best' GCR for a given broadcast time, i.e., given t, we want to find
parameters n, a, b, c, so that CRn(a,b,c) can inform all nodes
in time t (starting from 0, say), and such that n is as large as
possible. A variant of Ko's scheme is also used to answer this question.
When t is even, we succeed in finding n, a, b, c, with n equal to the
upper bound found by Ko, while when t is odd, we believe that two fewer
nodes are the best that can be achieved.
Associated labelings are also used in [9] to determine
the broadcast time of some double and triple step graphs; see also
[2,3].
In this section, we review the work of C.S. Ko [7,8], who gave
an optimal broadcast scheme for the triangular grid. This work is not
readily available, and we review it here briefly since we shall need
the details of the construction. Ko [7] also studied
other grids and grid-like graphs, and in particular was the first
to completely treat the usual square grids in two and three
dimensions; cf. also [11].
Figure 4: (a) The ball of radius 4 in the triangular grid.
(b) The same ball B4 in the re-drawn grid. (c) The even
balls B0, B2, B4, B6.
Before embarking on a discussion of broadcasting, we shall observe some
useful facts about the number of nodes in the ball Bi. To make the
calculations clearer, we shall look at the geometric dual of the
triangular grid, i.e., the infinite graph obtained by placing a node
in each triangular cell and making two nodes adjacent if the cells
share a side; see Figure 4(a). This is the so-called
beehive graph, in which adjacencies (and hence also the distances)
are the same as in the triangular grid.
The beehive graph can be drawn so as to make all
edges horizontal or vertical, and so each node (corresponding to a cell
of the grid) can be referred to by its cartesian coordinates. This is
illustrated in Figure 4(b). In Figure 4(a,b) we also illustrate the ball
B4, seen both as a set of cells in the grid, and a set of nodes in
the beehive graph.
We shall choose the coordinates so that v0=(0,0). We call level
Li the set Bi - Bi-1, i.e., the set consisting of all nodes of
distance exactly i to v0, and denote by L+i the subset of Li
consisting of all the nodes (x,y) Î Li with x > 0. Figure 4(b) shows
the set B4, with L4 marked by circles and L+4 marked by heavier
circles.
Proposition 2
For any integer i ³ 1,
|L+i|=i+ë(i-1)/2 û
|Li|=3i
|Bi|=1+[ 3/2]i(i+1)
Proof:
We only prove this when i is even. (The proof for i odd is similar.)
In this case, it is easy to see that L+i consists of the nodes
(1,i-1), (2,i-2), ..., (i/2,i/2), (i/2,i/2-2), (i/2,i/2-4), ..., (i/2,2-i/2), (i/2,-i/2), (i/2,4-i/2), ..., (1,1-i), implying the
first count. Note that (x,y) ® (1-x,y) is a bijection
between Li \L+i and L+i+1. Thus we have
|Li|=|L+i|+|L+i+1|=i+ë
i-1
2
û+(i+1)+ë
i
2
û = 3i.
Finally,
|Bi|=|L0|+|L1|+|L2|+¼+|Li|=1+3(1+2+¼+3i),
implying the last count. [¯]
We will now derive an upper bound on the number of nodes informed after t
time units, in any broadcast scheme on the triangular grid. Thus consider
an arbitrary broadcast scheme with originator v0=(0,0), and (without
loss of generality) the first call from v0 to v1=(1,0), and denote
by S(t) the set of nodes informed after t time units.
Partition S(t) into a set A of all those
informed nodes which are at distance at most t-3 from v0,
and the set B of informed nodes at distances greater than t-3.
(It will turn out that A can cover the entire Bt-3, but there
are necessarily uninformed nodes in Bi with i > t-3.)
Since A is a subset of Bt-3, we have from the above proposition
|A| £ 1+
3
2
(t-3)(t-2).
To estimate the number of nodes of the set B we use a different
approach: First, we note that there are no informed nodes at distance
to v0 greater than t (the available time) and at most one node
at distance t.
(It would have to be the unique node found by following the path obtained
from the call made at time 1, then the call made at time 2, etc.,
until the call made at time t, if this path does indeed lead
to a node at distance t.) Therefore it remains to count the number
of informed nodes in Lt-1 and Lt-2.
There are at most t informed nodes at distance t-1:
Indeed the path bringing the information to such a node follows the
calls made at times 1,2,..., i-1,i+1,i+2,...,t, and there are
only t possible choices for the value i. Finally, to count then
number of informed nodes in Lt-2, we first count those which
were informed through v1:
Since the distance to v0 is equal to the available time, all such
nodes (x,y) must have x > 0, and thus there are at most
|L+t-2| = t-2+ë[(t-3)/2]û of them. On the
other hand, those not informed through v1 must follow the path
of calls made at times 2, 3, ..., i-1, i+1, i+2, ..., t
and so there are at most t-1 of them. In conclusion, we have
This number is equal to (3/2)t2-4t+6 when t is even and
(3/2)t2-4t+(13/2) when t is odd.
Ko found a scheme which achieves this bound. Ko's scheme is
illustrated in Figure 5. There are variants illustrated
in Figures 10, 11, and 12. In all these schemes, the two nodes which
have the information at time 1 (called v0, v1 in the above
discussion) each initiate one path sending the information at times
2, 3, 4, ... and one path sending the information at times
3, 4, 5, .... These four paths (together with the edge
corresponding to the unique call at time 1) are marked
by heavy lines in the Figures 5, 10, 11, 12.
For instance, in Figure 5(a), v0 is seen to initiate the path
going up, then left, then up, then left, etc., corresponding to
calls made at times 2,3,4,5,..., and a path going down, then left,
then down, then left, etc., corresponding to calls made at times
3,4,5,6,....
The remaining vertices (not on these four paths) are informed by
subpaths emanating from each vertex of the main four paths, as soon
as possible after it had received and forwarded the information along
the main path.
For instance in figure 5(a), the vertex x just above v0 initiates
a path going up, up, up, etc., at times 4,5,6,..., while the
vertex y immediately to the left of x initiates a path going
down, then left, then down, then left, etc., at times 5,6,7,....
The differences between the variants are best seen
on the four main paths. To see that any of these schemes achieves
the above upper bound on |S(t)|, we note the following facts:
The scheme informs one node in level Lt, namely the unique node reached
by the path corresponding to the calls made at times 1, 2, ..., t;
it informs t nodes in Lt-1, namely each of the nodes reached by the paths
corresponding to the calls made at times 1, 2, ..., i-1, i+1, ..., t
(the scheme assures that these nodes are all distinct);
it informs t-1 nodes of Lt-2 via paths not going through v1, namely
the nodes reached by the paths corresponding to the calls made at times
2, 3, ..., i-1, i+1, ..., t; and finally
it informs all the nodes of L+t-2 and of all levels Li, i £ t-3.
Since these were the maximum possible counts on each level (according to the proof
of the upper bound given above), the scheme is optimal, and the bound is tight.
Figure 5: (a) An optimal broadcast scheme for the triangular grid.
(b) The shape of the region K(6). (c) All even regions
K(0), K(2), ..., K(8).
Figure 6: The odd case: (a) The balls B1, B3, B5, B7.
(b) The regions K(1), K(3), K(5), K(7). (c) The ball
B3 is contained in the region K(6).
This proves:
Theorem 1[7]
The maximum number of nodes in the triangular grid that can be
informed by broadcasting from one node in time t is equal to
[ 3/2]t2-4t+[ 13/2] when t is odd, and
[ 3/2]t2-4t+6 when t is even
It is an interesting conclusion from the above result, cf. [7],
that in the triangular grid (in the beehive graph) the maximum
number of cells (nodes) that can be informed in time t is not equal
to a polynomial in t. (It is conjectured to be a polynomial in grids
determined by a template of vectors in n-space, cf.
[5,6,12].)
Let us denote by K(t) the set of nodes informed by the basic Ko broadcast
scheme (as in Figure 5) in time t. We have marked, in the triangular grid
in Figure 5(b,c), the shape of the region consisting of all cells informed
by time t, t even. For odd t, the shape is illustrated in Figure 6(b).
In this section, we shall review the work of Morillo, Comellas, and Fiol
[10], who constructed the largest GCR's for a given diameter.
This reference is also not easily accessible and we include a sketch of
the construction, to the degree that we will need it.
Therefore suppose D is a fixed positive integer, and we are looking for
parameters n, a, b, c, so that CRn(a,b,c) has diameter D, and n is
as large as possible. We first derive an upper bound on n. Thus suppose we
have an arbitrary GCR G of diameter D, which is some CRn(a,b,c).
We estimate n in terms of D. According to Proposition 1, there is a
tile corresponding to G, which fits within BD, and hence G has at
most 1+(3/2)(D2+D) nodes, by Proposition 2. We can improve on this
bound by noting that our tile cannot fill all of BD:
Indeed, the nodes of V0 are associated with
triangles pointing up, i.e., with cells of levels Li with i even, and
the nodes of V1 with triangles pointing down, i.e., with cells on Li
with i odd.
Since |V0|=|V1|, we conclude that n is at
most twice the number of triangles pointing up (respectively down)
in BD. Suppose first that D is odd. Then, according to Proposition 2,
BD contains 1+3·2+3·4+¼+3·(D-1) triangles pointing up,
and so n is at most twice this number. Similarly, when D is even, BD
contains 3·1+3·2 +¼+3·(D-1) triangles
pointing down, and n is bounded by twice this number.
We obtain the bounds
n
£
2( 1+
D-1 å
i=2,even
3l) =
3D2+1
2
, Dodd
(1)
n
£
2
D-1 å
i=1,odd
3l =
3D2
2
, Deven
(2)
It was observed by the authors of [10], that, for D odd,
the graph GCRn(1,-1,3D) with n=[(3D2+1)/2] has diameter D,
whence these graphs are optimal, and the bound (1) is tight.
These authors also observed that, for D even,
the graph GCRn(1,-1,3D+1)
with n=[(3D2)/2] - D has diameter D.
It is generally believed that these graphs are optimal,
but the only firm
result in this direction is that the upper bound
n=[(3D2)/2] cannot
be attained [10]. For convenience we shall refer to them as
quasioptimal graphs.
In Figure 7 we illustrate a tile arising from
GCRn(1,-1,3D),
in (a),
and from
GCRn(1,-1,3D+1), in (b).
The tiles are the shaded
regions; as suggested in the figures, they can be used to tile the plane.
The figures also show how each tile fits within the ball of radius D
- marked here by the additional outline (compare also with Figures 4(c)
and 6(a)).
Figure 7: (a) The optimal tile for D=5 (and the outline of B5).
(b) The quasioptimal tile for D=6 (and the outline of B6).
In conclusion:
Theorem 2[13]
The maximum number of nodes in a generalized chordal ring of diameter
D is
equal to [(3D2+1)/2] when D is odd, and
at most [(3D2)/2] and at least [(3D2)/2]-D when D is
even.
We are interested in broadcasting in a generalized chordal ring.
As noted earlier, such broadcasts can be obtained from broadcasts
in the triangular grid. We derive the following general result:
Theorem 3
Every generalized chordal ring of diameter D admits a broadcast (from
any starting node) that informs all nodes in time at most D+2.
Proof: According to Proposition 1, every GCR G of diameter D
defines a tile T which is a subset of BD (as in Figures 7(a,b)).
Recall that the definition of this tile is not unique. It is easy to
see (compare Figures 4(c) with 6(b), and 6(a) with 5(c)) that each
BD is a subset of the set K(D+3) (of nodes informed
after time D+3 in Ko's scheme, cf. Figure 6(c))
- therefore we can broadcast in G in time at most D+3. To lower
the bound to D+2 we must take more care in choosing the tile T.
Specifically, we shall show that every GCR of diameter D admits
some tile which fits within the region K(D+2).
Recall that by definition n is even, and that every CRn(a,b,c)
admits a matching M in which each even i is matched with i+a. Also
recall that we can assume that a=1.
Suppose first that D is odd. Then as we have seen in the proof of
Theorem 2, T has more triangles pointing down than
pointing up, and so the broadcast cannot reach all of them. In fact, we
have a choice of which of these down triangles we choose to
represent an odd node of the GCR. We shall make these choices
following the matching M - placing the node 2j+1 always
adjacent to the node 2j. This matching rule is illustrated in
Figure 8.
Figure 8: The case of odd D: (a) A tile for CR(32,1,-1,9)
fits within B5.
(b) The same tile also fits within K(7).
It is easy to see that by following the above matching rule we find a tile
representing CRn(a,b,c) which does not use the lowest down triangles,
because of the matching we chose. (This is illustrated in
Figure 8(a).) Therefore, the new tile fits within K(D+2).
(Cf. Figure 8(b).) Hence we can inform all nodes of G in
time D+2.
When D is even, the argument is similar. In this case there are
more triangles pointing up than down, and we shall choose places to
represent even nodes of our GCR by respecting the matching that
matches each odd j with j-c. This is illustrated in Figure 9(a).
It is also easy to verify that such a tile, representing G, will
fit within K(D+2), as illustrated in Figure 9(b). This implies the
existence of a broadcast scheme which informs every node of
G in time D+2. [¯]
Figure 9: Even D: (a) A tile for CR(16,1,-1,7) fits within
B4.
(b) The same tile also fits within K(6).
We now observe that there are GCR's of diameter D for which the
minimum broadcast time is equal to D+2. Of course, the natural
candidates for this are GCR's which have as many nodes as possible
for the given D, and this is a good choice. When D is odd, then
the diameter-optimal GCR has [(3D2)/2]+[ 1/2] nodes by Theorem 2,
but we know from Theorem 1, that for t=D+1 (thus t even) we can reach
at most
3
2
(D+1)2-4(D+1)+6=
3D2
2
-D+
7
2
nodes. Therefore in this case D+2 is the best broadcast time possible.
We can also find GCR's of diameter D in which the optimal broadcast
time is D+1: Consider the quasioptimal GCR's with even diameter.
For a fixed even D such a graph has [(3D2)/2]-D nodes. It
is easy to modify Ko's basic broadcast scheme to inform all cells of
such a tile in time D+1. We illustrate the variant in Figure 10.
Therefore in this case a broadcast in time D+1 is possible.
It is again easy to verify that D+1 is the minimum: In time t=D
(D even), Theorem 1 implies we can reach at most
[ 3/2]D2-4D+6 nodes, fewer than in our GCR, according to Theorem 2.
Figure 10:
All cells of the quasioptimal tile for even diameter D
can be informed in time D+1.
It is also easy to construct GCR's of diameter D which admit a
broadcast informing all nodes (from any one chosen node) in
time D; for instance Cn(1,-1,3) is such a GCR.
5 Broadcast-optimality in generalized chordal
rings
Given a fixed broadcast time t, we seek a GCR with as many nodes
as possible, which admits a broadcast scheme informing all nodes in
time t.
Since we know optimal broadcast schemes in the triangular grid, we will
attempt to use tessellations to define optimal GCR's. Indeed, all we have
to do is find a shape which can be fully informed by some variant of Ko's
broadcast scheme (i.e., which includes all nodes informed by it in time
t), and which tessellates the plane.
(It has been proved in
[10] that each such tile corresponds to some CRn(a,b,c).)
First let t be odd. Consider the graph CRn(a,b,c), where
n=[(3t2)/2]-4t+[ 13/2], a=1, b=-3, c=[(3t-7)/2].
This GCR yields (in the usual way)
a tile which can be informed in time t by a modification of Ko's
scheme. The only unusual aspect of the modification is
a small adjustment made at two of the calls at time t
(the last time unit),
along the four main paths. These tiles, and variants of Ko's
broadcast scheme are illustrated in Figure 11; the adjusted calls
are marked by heaviest lines.
Figure 11: A tile that corresponds to optimal broadcast, for odd
broadcasting time.
For even values t, we do not have GCR's which match the
Ko bound, i.e., with [ 3/2]t2-4t+6 nodes,
and believe none are possible. GCR's with [ 3/2]t2-4t+4
nodes (recall that the number of nodes must be even)
are possible, and constructed along similar lines. The GCR's used
are CRn(a,b,c) with n=[ 3/2]t2-4t+4 and a=1, b=-1, c=[(3t-2)/2]. We illustrate the construction for t=6 and
t=8, in figure 12.
Theorem 4
For any t there exists a GCR with
[ 3/2]t2-4t+[ 13/2] nodes when t is odd, and
[ 3/2]t2-4t+4 nodes when t is even,
in which it is possible to inform all nodes in
time t by a broadcast from (any) one node.
Moreover when t is odd, it is not possible to inform
more nodes in time t in any GCR.
Figure 12: A tile that corresponds to the best known
broadcast, for even broadcasting time.
P. Morillo, F. Comellas, and M.A. Fiol,
The optimization of chordal ring networks,
Communication Technology, Eds. Q. Yasheng and W. Xiuying,
World Scientific, Singapore, 1987, ISBN 9971-50-349-9, pp. 295-299.
J.L.A. Yebra, M.A. Fiol, P. Morillo, and I.
Alegre,
The diameter of undirected graphs associated to plane
tessellations, Ars Combin.20B (1985), 159-172.
Footnotes:
1This research was supported by
a NATO Collaborative Research Grant (ref. 972241).
F.C. acknowledges research grants from
the Ministry of Science and Technology, Spain, and the
European Regional Development Fund (projects TIC2001-2171 and TIC2002-00155).
P.H. acknowledges a research grant from the
National Sciences and Engineering Research Council.
File translated from
TEX
by
TTH,
version 3.40. On 25 Jun 2003, 20:43.
