English  |  正體中文  |  简体中文  |  Items with full text/Total items : 69561/69561 (100%)
Visitors : 23281844      Online Users : 475
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
Scope Tips:
  • please add "double quotation mark" for query phrases to get precise results
  • please goto advance search for comprehansive author search
  • Adv. Search
    HomeLoginUploadHelpAboutAdminister Goto mobile version


    Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/8811


    Title: 快速有向性的Steiner Tree近似演算法;A Faster Approximation Algorithm for Directed Steiner Tree Problem
    Authors: 謝明益;Ming-I Hsieh
    Contributors: 資訊工程研究所
    Keywords: 群撥演算法;Multicast Routing;Steiner Tree
    Date: 2003-06-24
    Issue Date: 2009-09-22 11:35:13 (UTC+8)
    Publisher: 國立中央大學圖書館
    Abstract: 中文摘要: 在本論文中,我們提出一個新的有向性的Steiner Tree 近似演算法.Steiner Tree 的問題在於:給一個有向性的圖G=(V,E,c)這裡的c: E->R+ 是一個將邊轉換為值的函式,一個點的子集合(也就是terminals),及一個根vr ,有向性的Steiner Tree 問題在於如何尋找一個spanning tree 以根為起使點並連結到所有的terminals,並且使得spanning tree 上邊值的合為最小.DSP(Directed Steiner Tree Problem)常在一對多(Multicast)的資料傳送網路中被提起來改進其傳送時的成本.在本篇文章之前,Charikar 等人的DSP 演算法是在IDMR 方面最有名的.這個演算法能在O(n^lk^{2l-2}log n+m) 的時間內取得l(l-1)k^{1/l}的近似值的解(這裡的l 可是是任何大於1的值,n 是點的數量, 是邊的數量).不過這個演算法需要很大量的計算效能.而這份論文提供一個更快的近似演算法,能在O(P^n_lP^k_l+n^2k+nm)的時間內求得相同等級或更好的近似解. Abstract Given a weighted directed graph G = (V,E,c), where c : E -> R+ isan edge length function, a subset X of vertices (terminals), and a root vertex vr, directed Steiner tree problem (DSP) asks for a minimum cost tree which spans paths from root vertex vr to each terminal. DSP is often raised in one-to-many (Multicast) data delivering network to improve the cost of the distribution tree1. Before this article, Charikar et al’s DSP algorithm is well known for IDMR. It achieves an approximation ratio of 1(l−1)k^(1/l) in O(n^lk^{2l-2)logn+m) times for any fixed level l > 1, where l is the level of the tree produced by the algorithm, n is the number of vertices, |V |, and k is the number of terminals, |X|. Charikar et al’s DSP algorithm is useful to improve for IDMR. However it requires a great amount of computing power. This thesis provides a faster approximation algorithm based on ideas of Charikar et al’s DSP algorithm with better time complexity, O(P^n_lP^k_l+n^2k+nm), and a better approximation ratio for any level l > 1.
    Appears in Collections:[資訊工程研究所] 博碩士論文

    Files in This Item:

    File SizeFormat


    All items in NCUIR are protected by copyright, with all rights reserved.

    社群 sharing

    ::: Copyright National Central University. | 國立中央大學圖書館版權所有 | 收藏本站 | 設為首頁 | 最佳瀏覽畫面: 1024*768 | 建站日期:8-24-2009 :::
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback  - 隱私權政策聲明