The computational complexity of Steiner tree problems in graded matrices

T. Dudás, B. Klinz, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    4 Citations (Scopus)

    Abstract

    We investigate the computational complexity of the Steiner tree problem in graphs when the distance matrix is graded, i.e., has increasing, respectively, decreasing rows, or increasing, respectively, decreasing columns, or both. We exactly characterize polynomially solvable and NP-hard variants, and thus, establish a sharp borderline between easy and diffucult cases of this optimization problem.
    Original languageEnglish
    Pages (from-to)35-39
    Number of pages5
    JournalApplied Mathematics Letters
    Volume10
    Issue number4
    DOIs
    Publication statusPublished - 1997

    Fingerprint Dive into the research topics of 'The computational complexity of Steiner tree problems in graded matrices'. Together they form a unique fingerprint.

    Cite this