A Note on Broadcasting on the Arrangement Graph

Y.F. Li and K. Qiu (Canada)


broadcasting, neighbourhood broadcasting, arrangement graph, disjoint cycle.


The (n, k)-arrangement graph is a generalization of the well known star graph. We present a novel and op timal broadcasting algorithm with a running time of O(log(n!/(n − k)!))-time (=O(k log n)) for the (n, k) arrangement which is simpler than the current ones. To this end, we first present a neighbourhood broadcasting al gorithm for the graph. This algorithm is the first such an al gorithm and has an optimal running time of O(log k(n−k)) = O(log n), where 1 ≤ k ≤ n.

Important Links:

Go Back