English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54367/62174 (87%)
Visitors : 13852217      Online Users : 168
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTHU 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
    National Tsing Hua University Institutional Repository > 電機資訊學院 > 資訊工程學系 > 期刊論文 >  Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs


    Please use this identifier to cite or link to this item: http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/66263


    Title: Balancing minimum spanning trees and multiple-source minimum routing cost spanning trees on metric graphs
    Authors: Lin, Chung-Ming;Tsai, Yin Te;Tang, Chuan Yi
    教師: 唐傳義
    Date: 2006
    Publisher: Elsevier
    Relation: INFORMATION PROCESSING LETTERS,Volume 99,Issue 2,Pages 64-67,JUL 31 2006
    Keywords: Schematic diagrams
    Graph theory
    Cost accounting
    Routers
    Algorithms
    Balancing
    Abstract: Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1 + 2 / ( α - 1 ) times of that of an MST of G, and the k-source routing cost of T is at most α ( 1 + 2 ( k - 1 ) ( n - 2 ) / k ( n + k - 2 ) ) times of that of a k-MRCT of G with respect to S, where α > 1, k = | S | and n is the number of vertices of G.
    URI: http://www.elsevier.com/
    http://nthur.lib.nthu.edu.tw/dspace/handle/987654321/66263
    Appears in Collections:[資訊工程學系] 期刊論文

    Files in This Item:

    File Description SizeFormat
    index.html0KbHTML262View/Open


    在NTHUR中所有的資料項目都受到原著作權保護,僅提供學術研究及教育使用,敬請尊重著作權人之權益。若須利用於商業或營利,請先取得著作權人授權。
    若發現本網站收錄之內容有侵害著作權人權益之情事,請權利人通知本網站管理者(smluo@lib.nthu.edu.tw),管理者將立即採取移除該內容等補救措施。

    SFX Query

    與系統管理員聯絡

    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - Feedback