The Steiner tree problem on graphs: inapproximability results

Janka Chlebikova; M. Chlebik

doi:10.1016/j.tcs.2008.06.046

The Steiner tree problem on graphs: inapproximability results

Janka Chlebikova, M. Chlebik

School of Computing

Research output: Contribution to journal › Article › peer-review

358 Downloads (Pure)

Abstract

The Steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within a factor 96/95. Our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically providing gadgets and/or expanders with better parameters.

Original language	English
Pages (from-to)	207-214
Number of pages	8
Journal	Theoretical Computer Science
Volume	406
Issue number	3
DOIs	https://doi.org/10.1016/j.tcs.2008.06.046
Publication status	Published - 31 Oct 2008

Keywords

Steiner tree
graphs
approximation hardness

Access to Document

10.1016/j.tcs.2008.06.046

steiner-jour-revision.pdf

http://portal.acm.org/citation.cfm?id=1414105.1414423&coll=DL&dl=GUIDE&CFID=29403851&CFTOKEN=59301073

Cite this

@article{5f4546f209e3499aaf6a7b7013a601b6,

title = "The Steiner tree problem on graphs: inapproximability results",

abstract = "The Steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within a factor 96/95. Our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically providing gadgets and/or expanders with better parameters.",

keywords = "Steiner tree, graphs, approximation hardness",

author = "Janka Chlebikova and M. Chlebik",

note = "Funders: VEGA grant no. 1/3106/06 (Slovakia).",

year = "2008",

month = oct,

day = "31",

doi = "10.1016/j.tcs.2008.06.046",

language = "English",

volume = "406",

pages = "207--214",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - The Steiner tree problem on graphs: inapproximability results

AU - Chlebikova, Janka

AU - Chlebik, M.

N1 - Funders: VEGA grant no. 1/3106/06 (Slovakia).

PY - 2008/10/31

Y1 - 2008/10/31

N2 - The Steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within a factor 96/95. Our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically providing gadgets and/or expanders with better parameters.

AB - The Steiner tree problem on weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within a factor 96/95. Our inapproximability results are stated in a parametric way, and explicit hardness factors would be improved automatically providing gadgets and/or expanders with better parameters.

KW - Steiner tree

KW - graphs

KW - approximation hardness

U2 - 10.1016/j.tcs.2008.06.046

DO - 10.1016/j.tcs.2008.06.046

M3 - Article

SN - 0304-3975

VL - 406

SP - 207

EP - 214

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 3

ER -

The Steiner tree problem on graphs: inapproximability results

Abstract

Keywords

Access to Document

Fingerprint

Cite this