@inproceedings{03d13756c8d944f38b0706a73432a277,
title = "MAX-SNP hardness and approximation of selected-internal steiner trees",
abstract = "In this paper, we consider an interesting variant of the well-known Steiner tree problem: Given a complete graph G = (V, E) with a cost function c : E → R+ and two subsets R and R′ satisfying R′ ⊂ R ⊆ V, a selected-internal Steiner tree is a Steiner tree which contains (or spans) all the vertices in R such that each vertex in R′ cannot be a leaf. The selected-internal Steiner tree problem is to find a selected-internal Steiner tree with the minimum cost. In this paper, we show that the problem is MAX SNP-hard even when the costs of all edges in the input graph are restricted to either 1 or 2. We also present an approximation algorithm for the problem.",
author = "Hsieh, {Sun Yuan} and Yang, {Shih Cheng}",
year = "2006",
month = jan,
day = "1",
doi = "10.1007/11809678_47",
language = "English",
isbn = "3540369252",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "449--458",
booktitle = "Computing and Combinatorics - 12th Annual International Conference, COCOON 2006, Proceedings",
address = "Germany",
note = "12th Annual International Conference on Computing and Combinatorics, COCOON 2006 ; Conference date: 15-08-2006 Through 18-08-2006",
}