English  |  正體中文  |  简体中文  |  Items with full text/Total items : 54367/62174 (87%)
Visitors : 14556213      Online Users : 52
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
    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/
    Appears in Collections:[資訊工程學系] 期刊論文

    Files in This Item:

    File Description SizeFormat


    SFX Query


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