Wu, B.Y.B.Y.WuHsiao, C.Y.C.Y.HsiaoKUN-MAO CHAO2018-09-102018-09-10200801784617https://www.scopus.com/inward/record.uri?eid=2-s2.0-38149023352&doi=10.1007%2fs00453-007-9080-z&partnerID=40&md5=a73af5cfc7f56664413d835f62baffechttp://scholars.lib.ntu.edu.tw/handle/123456789/339638Let 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.Algorithm; Graph; Optimization problem; Spanning tree; Swap edgeOptimization problem; Spanning trees; Swap edges; Algorithms; Edge detection; Number theory; Optimization; Problem solving; Trees (mathematics)journal article10.1007/s00453-007-9080-z2-s2.0-38149023352