The Steiner tree problem on graphs: Inapproximability results

Chlebík, Miroslav and Chlebíková, Janka (2008) The Steiner tree problem on graphs: Inapproximability results. Theoretical Computer Science, 406 (3). pp. 207-214. ISSN 0304-3975

Full text not available from this repository.

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 by providing gadgets and/or expanders with better parameters.

Item Type: Article
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 20:28
Last Modified: 04 Apr 2012 13:30
URI: http://sro.sussex.ac.uk/id/eprint/26053
📧 Request an update