본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Design of Survivable Communication Networks with High-connectivity Constraints

Koh, Seok J.    (Graduate School of Management, KAIST   ); Lee, Chae Y.    (Department of Industrial Management, Korea Advanced Institute of Science and Technology  );
  • 초록

    Designing highly survivable interoffice telecommunication networks is considered. The problem is formulated as a minimum-cost network design problem with three node connectivity constraints. These valid and facet-defining inequalities for the convex hull of the solution are presented. A branch and cut algorithm is proposed based on the inequalities to obtain the optimal solution. With the lower bound by the cutting plane algorithm, a delete-ink heuristic is proposed to otain a good upper bound in the branch and bound procedure. The effeciveness of the branch and cut algorithm is demonstrated with computational results for a variety of problem sets : different lower bounds, two types of link costs and large number of links. The cutting plane procedure based on the three inequalities provides excellent lower bounds to the optimal solutions.


  • 참고문헌 (16)

    1. Computer-Aided Design Procedures for Survivable Fiber Optic Networks , Cardwell, R. H.;C. L. Monma;T. H. Wu , IEEE Journal on Selected Areas in Communications / v.7,pp.1188-1197,
    2. Dividing a Graph into Triconnected Components , J. Hopcropt;R. E. Tarjan , SIAM Journal on Computing / v.2,pp.135-158,
    3. A Smallest 3-Connectivity Augmentation of a Graph , T. Watanabe;A. Nakamura , Discrete Applied Mathematics / v.28,pp.183-186,
    4. T. H. Wu , Fiber Network Service Survivability / v.,pp.,
    5. Computational Results with a Cutting Plane Algorithm for Designing Communication Networks with Low Connectivity Constraints , M. Groetschel;C. L. Monma;M. Stoer , Operations Research / v.40,pp.309-330,
    6. Integer Polyhedra Associated with Certain Network Design Problems with Connectivity Constraints , M. Groetschel;C. L. Monma , SIAM Journal on Discrete Mathematics / v.3,pp.502-523,
    7. Minimum-weight Two-connected Spanning Networks , C. L. Monma;B. S. Munson;W. R. Pulleyblank , Mathematical Programming / v.46,pp.153-171,
    8. 3-Connectivity Augmentation Problems , T. Watanabe;A. Nakamura , Proceeding of IEEE International Symposium on Circuits and Systems / v.,pp.1847-1850,
    9. A Minimum 3-Connectivity Augmentation of a Graph , T. Watanabe;A. Nakamura , Journal of Computer and System Sciences / v.46,pp.91-128,
    10. On the Structure of Minimum-Weight k-connected Spanning Networks , Bienstock, D.;E. F. Brickell;C. L. Monma , SIAM Journal on Discrete Mathematics / v.3,pp.320-329,
    11. Methods for Designing Communications Networks with Certain Two-connected Survivability Constraints , C. L. Monma;D. F. Shallcross , Operations Research / v.37,pp.531-541,
    12. Algorithm 447: Efficient Algorithms for Graph Manipulation , J. Hopcropt;R. E. Tarjan , Communications of ACM / v.16,pp.372-378,
    13. Polyhedra of the Equivalent Subgraph Problem and Some Edge Connectivity Problems , S. Chopra , SIAM Journal on Discrete Mathematics / v.5,pp.321-337,
    14. Multi-Therminal Network Flows , R. E. Gomory;T. C. Hu , SIAM Journal on Applied Mathematics / v.9,pp.551-570,
    15. Facets for polyhedra arising in the design of communication networks with low-connectivity constraints , M. Groetschel;C. L. Monma;M. Stoer , SIAM Journal on Optimization / v.2,pp.474-504,
    16. An efficient Algorithm for the Minimum Capacity Cut Problem , M. Padberg;G. Rinaldi , Mathematical Programming / v.47,pp.19-36,

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
  • 한국경영과학회 : 저널
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기