Broadcasting in weighted-vertex graphs

In this thesis, we present a new model for information dissemination in communication networks. The model is defined on networks in which nodes are assigned some weights representing the internal delay they should pass before sending data to their neighbors. The new model, called weighted-vertex model, comes to have real world applications in parallel computation and satellite terrestrial networks. Broadcasting in weighted-vertex model is a generalized version of classical broadcasting problem, which is NP_Complete. The problem remains NP_Complete in some classes of weighed-vertex graphs. We show existence of approximation algorithms for the broadcasting problem in weighted vertex model, as well as better approximations for specific subclasses of weighted graphs. In addition we study broadcasting in complete weighted graphs and present an algorithm for finding the optimum solution in this case. Broadcasting in complete graphs with uniform weights is studied separately. Finally we introduce some heuristics for the problem and compare their performance using computer simulations