University of Taipei:Item 987654321/16014
English  |  正體中文  |  简体中文  |  全文笔数/总笔数 : 2471/17084 (14%)
造访人次 : 3184793      在线人数 : 947
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧：
  • 您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果
  • 若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据
    •  进阶搜寻
    University of Taipei > 理學院 > 資訊科學系 > 期刊論文 >  Item 987654321/16014


    jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://utaipeir.lib.utaipei.edu.tw/dspace/handle/987654321/16014


    题名: The bottleneck selected-internal and partial terminal Steiner tree problems
    作者: Chen, Yen-Hung;陳彥宏
    贡献者: 臺北市立大學資訊科學系
    日期: 2016-10
    上传时间: 2017-07-31 13:51:18 (UTC+8)
    摘要: Given a complete graph G = (V, E) math formula, a positive length function on edges, and two subsets R of V and math formula of R, the selected-internal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that no vertex in math formula is a leaf of the subgraph. The bottleneck selected-internal Steiner tree problem is to find a selected-internal Steiner tree T for R and math formula in G such that the length of the largest edge in T is minimized. The partial terminal Steiner tree is defined to be an acyclic subgraph of G spanning all vertices in R such that each vertex in math formula is a leaf of the subgraph. The bottleneck partial terminal Steiner tree problem is to find a partial terminal Steiner tree T for R and math formula in G such that the length of the largest edge in T is minimized. In this article, we show that the bottleneck selected-internal Steiner tree problem is NP-complete. We also show that if there is a math formula-approximation algorithm, math formula, for the bottleneck selected-internal Steiner tree problem on metric graphs (i.e., a complete graph and the lengths of edges satisfy the triangle inequality), then P=NP. Then we extend to show that if there is an math formula-approximation algorithm, math formula, for the bottleneck selected-internal Steiner tree problem, then P=NP, where math formula is any computable function of math formula. Moreover, we present an approximation algorithm with performance ratio of 3 for the bottleneck selected-internal Steiner tree problem on metric graphs. Finally, we present an exact algorithm of math formula time for the bottleneck partial terminal Steiner tree problem.
    關聯: Networks，Vol. 68(4)，P.331-339
    显示于类别:[資訊科學系] 期刊論文

    文件中的档案:

    没有与此文件相关的档案.



    在uTaipei中所有的数据项都受到原著作权保护.

    如有問題歡迎與系統管理員聯繫
    02-23113040轉2132
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈