ABSTRACT
This chapter presents several problems on finding disjoint paths for reliable communications. First, the basic problem of finding a set of disjoint routes whose total cost is minimized, which is called a MIN-SUM problem, is considered. Several approaches, which include integer linear programming (ILP), a disjoint shortest pair algorithm, and the Suurballe algorithm, are introduced to solve the problem. Second, the MIN-SUM problem in a network with shared risk link groups (SRLGs) and its solutions are presented. Third, the MIN-SUM problem in a multiple-cost network and its solutions are introduced.
