The swap edges of a multiple-sources routing tree
Date Issued
2005
Date
2005
Author(s)
Hsiao, Chih-Yuan
DOI
en-US
Abstract
Let T be a spanning tree of a graph G and S V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this thesis, we propose an O(mlogn+n2)-time algorithm for the case of two sources and an algorithm with time complexity O(mn) for the case of more than two sources, in which m and n are the numbers of edges and vertices of G, respectively.
Subjects
路由樹
替代邊
生成樹
spanning tree
routing tree
swap edge
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92922057-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):e495b4881703ea6a4b6564cc07bc518d