## Abstract

We consider a generalization of both the classic Steiner tree problem and the terminal Steiner tree problem. Given a complete graph G = (V,E) with a metric cost function c:E BBQ≥ and two proper subsets R V and R′ R , a partial-terminal Steiner tree is a Steiner tree which contains all vertices in it R such that all vertices in R ′ must be leaves. The partial-terminal Steiner tree problem is to find a partial-terminal Steiner tree of the minimum cost in G. The previously best-known approximation ratio of the problem is 2ρ , where ρ is the approximation ratio of the Steiner tree problem. In this paper, we improve the ratio from 2ρ to 2ρ-ρ3ρ-2-f , where f is a non-negative function whose value is between 0 and ρ-ρ over 3ρ-2.

Original language | English |
---|---|

Article number | 6636895 |

Pages (from-to) | 274-279 |

Number of pages | 6 |

Journal | IEEE Transactions on Computers |

Volume | 64 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2015 Jan 1 |

## All Science Journal Classification (ASJC) codes

- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics