Applications of graph theory in communication networks

Good communication between the units in a communication network or among the proccessors in a parallel system is essential for the proper functioning. There are various problems of communication that can be transformed to the problems of graph theory. Since several of these problems are NP-hard, we focus on solving subproblems which can be solved in polynomial time. One of popular problems of information dissemination is broadcasting. Broadcasting is the process of dissemination of a message from one vertex (called originator) to all other vertices in the graph. This task is accomplished by placing a sequence of calls between neighboring vertices while we follow some rules. In disertation broadcasting in cactus graphs is studied. An algorithm that determines broadcast time of any originator with time complexity О(nlog Delta) in k-restricted cactus graph is given. Furthermore, another algorithm which calculates broadcast time of all vertices in a k-restricted cactus graph and optimal broadcast scheme for each vertex of a graph within the same time complexity is outlined. As a byproduct, broadcast center of a k-restricted cactus graph is computed.;In the second part of disertation we will talk about another problem associated with communication networks. We will introduce modified Wiener number on directed graphs and we will study digraphs with minimal value for one possible modification of the Wiener number for directed graphs. For digraphs with unique shortest paths we provide minimal digraphs for alpha 1, and give some partial results for 0< alpha <0.