H.A. Harutyunyan and C.D. Morosan (Canada)
Networks, minimum broadcast time, iterative algorithms.
Broadcasting is the problem of dissemination of informa tion in which one piece of information needs to be trans mitted to a group of individuals connected by an intercon nection network. Finding an optimum strategy for broad casting, 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 net work, 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 n2 s pace, where k is the number of iterations, n the number of vertices, and m the number of edges.
Important Links:
Go Back
