Title of article :
More broadcast graphs Original Research Article
Author/Authors :
Hovhannes A Harutyunyan، نويسنده , , Arthur L. Liestman، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1999
Pages :
22
From page :
81
To page :
102
Abstract :
Given a graph G=(V,E) and a vertex u∈V, broadcasting is the process of disseminating a piece of information from vertex u to every other vertex in the graph where, in each time unit, any vertex which knows the information can pass the information to at most one of its neighbors. A broadcast graph on n vertices is a graph which allows any vertex to broadcast in time ⌈log n⌉. A minimum broadcast graph on n vertices is a broadcast graph with the minimum number of edges over all broadcast graphs on n vertices. This minimum number of edges is denoted by B(n). Several papers have presented techniques to construct broadcast graphs for various n and, hence, upper bounds on B(n). In this paper, we present new techniques to construct broadcast graphs that give improved upper bounds for 5417 values of n in the range 1⩽n⩽214 and for most values of n⩾220. These graphs can be combined using some of the previous methods to produce further improvements.
Journal title :
Discrete Applied Mathematics
Serial Year :
1999
Journal title :
Discrete Applied Mathematics
Record number :
884994
Link To Document :
بازگشت