University of Taipei:Item 987654321/16014
English  |  正體中文  |  简体中文  |  全文筆數/總筆數 : 2471/17084 (14%)
造訪人次 : 3189484      線上人數 : 1007
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜尋範圍 查詢小技巧：
  • 您可在西文檢索詞彙前後加上"雙引號"，以獲取較精準的檢索結果
  • 若欲以作者姓名搜尋，建議至進階搜尋限定作者欄位，可獲得較完整資料
    •  進階搜尋
    University of Taipei > 理學院 > 資訊科學系 > 期刊論文 >  Item 987654321/16014


    請使用永久網址來引用或連結此文件: 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 ©   - 回饋