GRAPH-THEORETICAL ISSUES IN COMPUTER-NETWORKS

Recently computer networks have become one of the main topics of resea rch in computer science. This fact has been motivated by their increas ing importance in all applications involving distributed systems. Grap h theory remains the main theoretical tool for design and analysis of such networks. This survey is concerned with basic graph theoretical i ssues arising in the above context. The first set of problems is conce rned with network decomposition and locality of distributed algorithms . Among others, diameter decomposition, routing schemes with a small s tretch factor and a construction of graph spanners are consisdered. Th en, gossiping and broadcasting problems are discussed and the best alg orithms are presented. As the last problem a construction of fault-tol erant routing schemes is presented.