James P. Brumbaugh-Smith

Department of Mathematics and Computer Science

Manchester College

North Manchester, IN 46962-1276

Douglas R. Shier

Department of Mathematical Sciences

Clemson University

Clemson, SC 29634-0975

Abstract: An important task in the management and administration of communication networks is constructing routes for messages to follow from source to destination. A common approach is to route along the shortest available path connecting the source to the destination, where link lengths can be defined in a variety of ways (e.g., time, cost, impact on average queueing delay, or capacity required). This paper presents a family of novel minimax models for determining a set of paths from the source to the destination that are reasonably short in length while also reasonably diverse (disjoint). The overall goal is to design a routing scheme that is both efficient and robust, resulting in greater network reliability. Several models are investigated and a column-generation approach is proposed for exact solution. Computational results show that this exact technique can be applied effectively to moderate sized networks. For even larger networks, heuristic methods are developed and tested.

Key Words: bicriterion networks, communications, games, linear programming