Graph theoretical issues in computer networks

Recently computer networks have become one of the main topics of research in computer science. This fact has been motivated by their increasing importance in all applications involving distributed systems. Graph theory remains the main theoretical tool for design and analysis of such networks. This survey is concerned with basic graph theoretical issues arising in the above context. The first set of problems is concerned with network decomposition and locality of distributed algorithms. Among others, diameter decomposition, routing schemes with a small stretch factor and a construction of graph spanners are considered. Then, gossiping and broadcasting problems are discussed and the best algorithms are presented. As the last problem a construction of fault-tolerant routing schemes is presented.