University of Sussex
Browse

File(s) not publicly available

The Steiner tree problem on graphs: Inapproximability results

journal contribution
posted on 2023-06-08, 06:22 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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 by providing gadgets and/or expanders with better parameters.

History

Publication status

  • Published

Journal

Theoretical Computer Science

ISSN

0304-3975

Issue

3

Volume

406

Page range

207-214

Pages

8.0

Department affiliated with

  • Mathematics Publications

Full text available

  • No

Peer reviewed?

  • Yes

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC