In this paper, we present a heuristic algorithm for k-broadcasting in an arbitrary network. This heuristic generates optimal k-broadcast time in grid graph when k ≥ 2. In two-dimensional torus graph, it also generates optimal k-broadcast time when k ≥ 3, while giving a bound of 「m/2」 + 「n/2」 + 1 when k = 2, where m and n are the number of rows and columns in the graph. In practice, the new heuristic outperforms best known I-broadcast algorithm for three different network design models. The new algorithm runs fast. The time complexity of the algorithm is O(R·m), where R represents the rounds of broadcasting, and m stands for the total number of edges in the graph.
展开▼