The full Steiner tree problem
| dc.citation.epage | 67 | en_US |
| dc.citation.issue | 1-3 | en_US |
| dc.citation.spage | 55 | en_US |
| dc.citation.volume | 306 | en_US |
| dc.citation.woscount | 20 | |
| dc.contributor.author | Lu, CL | en_US |
| dc.contributor.author | Tang, CY | en_US |
| dc.contributor.author | Lee, RCT | en_US |
| dc.contributor.department | 生物科技學系 | zh_TW |
| dc.contributor.department | Department of Biological Science and Technology | en_US |
| dc.date.accessioned | 2014-12-08T15:40:20Z | |
| dc.date.available | 2014-12-08T15:40:20Z | |
| dc.date.issued | 2003-09-05 | en_US |
| dc.description.abstract | Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R subset of V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either I or 2. For the instances with lengths either I or 2, we give a 8/5-approximation algorithm to find an approximate solution for the problem. (C) 2003 Elsevier B.V. All rights reserved. | en_US |
| dc.identifier.doi | 10.1016/S0304-3975(03)00209-3 | en_US |
| dc.identifier.issn | 0304-3975 | en_US |
| dc.identifier.journal | THEORETICAL COMPUTER SCIENCE | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1016/S0304-3975(03)00209-3 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/27537 | |
| dc.identifier.wosnumber | WOS:000185261500004 | |
| dc.language.iso | en_US | en_US |
| dc.subject | full Steiner tree problem | en_US |
| dc.subject | phylogenetic tree | en_US |
| dc.subject | evolutionary tree | en_US |
| dc.subject | NP-complete | en_US |
| dc.subject | MAX SNP-hard | en_US |
| dc.subject | approximation algorithm | en_US |
| dc.title | The full Steiner tree problem | en_US |
| dc.type | Article | en_US |