A branch and cut algorithm for a Steiner tree-star problem

Youngho Lee, Steve Y. Chiu, Jennifer Ryan

    Research output: Contribution to journalArticlepeer-review

    35 Citations (Scopus)

    Abstract

    This paper deals with a Steiner tree-star problem that is a special case of the degree constrained node-weighted Steiner tree problem. This problem arises in the context of designing telecommunications networks for digital data service, provided by regional telephone companies. In this paper, we develop an effective branch and cut procedure coupled with a suitable separation procedure that identifies violated facets for fractional solutions to the relaxed formulation. Computational results indicate that large problem instances with up to 200 nodes can be solved within acceptable time bounds.

    Original languageEnglish
    Pages (from-to)194-201
    Number of pages8
    JournalINFORMS Journal on Computing
    Volume8
    Issue number3
    DOIs
    Publication statusPublished - 1996

    Keywords

    • Branch and cut
    • Digital data networks
    • Node-weighted Steiner tree
    • Polyhedral structure
    • Telecommunications networks

    ASJC Scopus subject areas

    • Software
    • Information Systems
    • Computer Science Applications
    • Management Science and Operations Research

    Fingerprint

    Dive into the research topics of 'A branch and cut algorithm for a Steiner tree-star problem'. Together they form a unique fingerprint.

    Cite this