AN ITERATIVE ALGORITHM FOR THE MINIMUM BROADCAST TIME PROBLEM

摘要

Broadcasting is the problem of dissemination of information in which one piece of information needs to be transmitted to a group of individuals connected by an interconnection network. Finding an optimum strategy for broadcasting, such that this process is accomplished in minimum time, has been proven to be NP-complete, for an arbitrary network. Therefore, some heuristic algorithms have been developed for finding the minimum broadcast time of a network, usually modelled as a simple graph. To our knowledge, the best known heuristic works in O (Rnm), for the entire graph, where R is the approximate broadcasting time, n is the number of vertices, and m is the number of edges. In this paper we propose a global, iterative heuristic for finding the minimum broadcast time for the entire graph, being the first algorithm of this kind in the area. The algorithm uses a new interesting property of the optimal broadcast schemes that we have found. The algorithm behaves well in practice, especially for strongly irregular topologies, working in O (knm) time and O (n{sup}2) space, where k is the number of iterations, n the number of vertices, and m the number of edges.