Efficient construction of broadcast graphs

Abstract: A broadcast graph is a connected graph,

G = (V, E)

,

| V | = n

, in which each vertex can complete broadcasting of one message within at most

t = l c e i l l o g n c e i l

time units. A minimum broadcast graph on

n

vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on

n

vertices. The cardinality of the edge set of such a graph is denoted by

B (n)

. In this paper we construct a new broadcast graph with

B (n) l e (k + 1) N - (t - f r a c k 2 + 2) 2^{k} + t - k + 2

, for

n = N = (2^{k} - 1) 2^{t + 1 - k}

and

B (n) l e (k + 1 - p) n - (t - f r a c k 2 + p + 2) 2^{k} + t - k - (p - 2) 2^{p}

, for

2^{t} < n < (2^{k} - 1) 2^{t + 1 - k}

, where

t g e q 7

,

2 l e k l e l f l o o r t / 2 f l o o r - 1

for even

n

and

2 l e k l e l c e i l t / 2 c e i l - 1

for odd

n

,

d = N - n

,

x = l f l o o r f r a c d 2^{t + 1 - k} f l o o r

and

p = l f l o o r l o g_{2} (x + 1) f l o o r

if

x > 0

and

p = 0

if

x = 0

. The new bound is an improvement upon the bound presented by Harutyunyan and Liestman (2012) for odd values of

n

.

Recommendations

Cites work

Cited in

(28)

This page was built for publication: Efficient construction of broadcast graphs