https://scholars.lib.ntu.edu.tw/handle/123456789/339638
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.author | Wu, B.Y. | en_US |
dc.contributor.author | Hsiao, C.Y. | en_US |
dc.contributor.author | KUN-MAO CHAO | en_US |
dc.creator | Wu, B.Y.,;Hsiao, C.Y.,;Chao, K.-M. | - |
dc.date.accessioned | 2018-09-10T06:59:53Z | - |
dc.date.available | 2018-09-10T06:59:53Z | - |
dc.date.issued | 2008 | - |
dc.identifier.issn | 01784617 | - |
dc.identifier.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-38149023352&doi=10.1007%2fs00453-007-9080-z&partnerID=40&md5=a73af5cfc7f56664413d835f62baffec | - |
dc.identifier.uri | http://scholars.lib.ntu.edu.tw/handle/123456789/339638 | - |
dc.description.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 paper, we propose an O(mlog∈n+n 2)-time algorithm for the case of two sources and an O(mn)-time algorithm for the case of more than two sources, where m and n are the numbers of edges and vertices of G, respectively. © 2007 Springer Science+Business Media, LLC. | - |
dc.language | en | en |
dc.relation.ispartof | Algorithmica (New York) | - |
dc.source | AH | - |
dc.subject | Algorithm; Graph; Optimization problem; Spanning tree; Swap edge | - |
dc.subject.other | Optimization problem; Spanning trees; Swap edges; Algorithms; Edge detection; Number theory; Optimization; Problem solving; Trees (mathematics) | - |
dc.title | The swap edges of a multiple-sources routing tree | - |
dc.type | journal article | en |
dc.identifier.doi | 10.1007/s00453-007-9080-z | - |
dc.identifier.scopus | 2-s2.0-38149023352 | - |
dc.relation.pages | 299-311 | - |
dc.relation.journalvolume | 50 | - |
dc.relation.journalissue | 3 | - |
item.openairecristype | http://purl.org/coar/resource_type/c_6501 | - |
item.openairetype | journal article | - |
item.grantfulltext | none | - |
item.cerifentitytype | Publications | - |
item.fulltext | no fulltext | - |
crisitem.author.dept | Networking and Multimedia | - |
crisitem.author.dept | Biomedical Electronics and Bioinformatics | - |
crisitem.author.dept | Computer Science and Information Engineering | - |
crisitem.author.orcid | 0000-0003-2837-1279 | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
crisitem.author.parentorg | College of Electrical Engineering and Computer Science | - |
顯示於: | 生醫電子與資訊學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。