ON EFFICIENCY OF PATH SYSTEMS INDUCED BY ROUTING AND COMMUNICATION SCHEMES

Abstract

Communication problems are studied as simple directed path systems satisfying given communication requests in point-to-point networks. Efficiency measures of these path systems such as congestion, dilation, compactness and buffer-size are analyzed. We focus on some recent algorithmic developments and novel techniques for the design of efficient communication schemes. Related open problems and an overview of several related research directions are also given.