Paper Info
Title
Near Optimal Broadcasting in Optimal Triple Loop Graphs
Abstract
Triple loop networks (graphs) are generalizations of the ring topology where every vertex v is linked to 6 vertices v 卤 a, v 卤 b, v 卤 c. In this paper, we study the broadcast problem in optimal triple loop graphs. In 1987 for a restricted case a = -(b + c) the (maximum) number of vertices in the sub-optimal Triple loop graph has been proved to be aquadratic function of diameter d. In 1998 the broadcast time of this graph is proved to be d + 3. Recently, in 2003 the Optimal Triple Loop Graph in general was constructed, where its number of vertices is a cubic function of d. In this paper we prove d + 2 lower bound and d + 5 upper bound for broadcasting in general Optimal Triple Loop Graph. We also generalize our upper bound algorithm in Multiple Loop Graphs giving d + 2k - 1 general upper bound where the degree of every vertex is 2k.
Year
DOI
Venue
2008
10.1109/AINA.2008.83
AINA
Keywords
Field
DocType
aquadratic function,broadcast problem,sub-optimal triple loop graph,optimal triple loop graph,general optimal triple loop,multiple loop,triple loop network,upper bound algorithm,optimal triple loop graphs,optimal broadcasting,vertices v,vertex v,lower bound,network topology,routing,graph theory,computer science,parallel processing,application software,broadcasting,ring topology,software engineering,algorithm design and analysis,upper bound,local area networks
Indifference graph,Bound graph,Loop (graph theory),Computer science,Chordal graph,Independent set,Symmetric graph,1-planar graph,Pancyclic graph,Distributed computing
Conference
Citations 
PageRank 
References 
0
0.34
6
Authors
2
Name
Order
Citations
PageRank
Hovhannes A. Harutyunyan120628.18
Edward Maraachlian2183.09