Polyhedral and computational investigations for designing communication networks with high survivability requirements
成果类型：
Article
署名作者：
Grotschel, M; Monma, CL; Stoer, M
署名单位：
Telcordia Technologies; Zuse Institute Berlin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.6.1012
发表日期：
1995
页码：
1012-1024
关键词：
摘要：
We consider the important practical and theoretical problem of designing a low-cost communications network which can survive failures of certain network components. Our initial interest in this area was motivated by the need to design certain ''two-connected'' survivable topologies for fiber optic communication networks of interest to the regional telephone companies. In this paper, we describe some polyhedral results for network design problems with higher connectivity requirements. We also report on some preliminary computational results for a cutting plane algorithm for various real-world and random problems with high connectivity requirements, which shows promise for providing good solutions to these difficult problems.