Design of survivable networks / Mechthild Stoer

Auteur: Stoer, Mechthild (1963-) - AuteurType de document: Livre numériqueCollection: Lecture notes in mathematics, (Online) ; 1531Langue: anglaisÉditeur: Berlin : Springer-Verlag, 1992 ISBN: 9783540475002 ISSN: 1617-9692Note: 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) Sujets MSC: 90C27 Operations research, mathematical programming -- Mathematical programming -- Combinatorial optimization
90B18 Operations research, mathematical programming -- Operations research and management science -- Communication networks
90C10 Operations research, mathematical programming -- Mathematical programming -- Integer programming
90C35 Operations research, mathematical programming -- Mathematical programming -- Programming involving graphs or networks
94C15 Information and communication, circuits -- Circuits, networks -- Applications of graph theory
En-ligne: Springerlink | Zentralblatt | MathSciNet

No physical items for this record


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)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |