The computational complexity of Steiner tree problems in graded matrices

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

doi:10.1016/S0893-9659(97)00056-6

The computational complexity of Steiner tree problems in graded matrices

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

Research output: Contribution to journal › Article › Academic › peer-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 language	English
Pages (from-to)	35-39
Number of pages	5
Journal	Applied Mathematics Letters
Volume	10
Issue number	4
DOIs	https://doi.org/10.1016/S0893-9659(97)00056-6
Publication status	Published - 1997

Access to Document

10.1016/S0893-9659(97)00056-6

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

@article{b2e8dca286d7447b9ee8c1b281e54bde,

title = "The computational complexity of Steiner tree problems in graded matrices",

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.",

author = "T. Dud{\'a}s and B. Klinz and G.J. Woeginger",

year = "1997",

doi = "10.1016/S0893-9659(97)00056-6",

language = "English",

volume = "10",

pages = "35--39",

journal = "Applied Mathematics Letters",

issn = "0893-9659",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - The computational complexity of Steiner tree problems in graded matrices

AU - Dudás, T.

AU - Klinz, B.

AU - Woeginger, G.J.

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

U2 - 10.1016/S0893-9659(97)00056-6

DO - 10.1016/S0893-9659(97)00056-6

M3 - Article

VL - 10

SP - 35

EP - 39

JO - Applied Mathematics Letters

JF - Applied Mathematics Letters

SN - 0893-9659

IS - 4

ER -