Design of survivable networks / Mechthild Stoer

The problem of finding an "optimal'' communication network that meets various topological requirements (number of disjoint paths between nodes, and so on) is both important and difficult. This monograph addresses the problem from a polyhedral point of view: What set of linear constraints results in valid communication networks? A number of valid inequalities and facets are found for problems with either node or edge connectivity requirements. These classes of inequalities define the feasible polytope for small problems and seem to be excellent approximations for larger ones. The monograph concludes with a section on implementing a cutting plane algorithm and has a small number of solved instances. In addition to being a thorough examination of this problem, the techniques and approach comprise an excellent example of the polyhedral and cutting plane approach to solving combinatorial optimization models. (MathSciNet)