首页 | 本学科首页   官方微博 | 高级检索  
     


Reconstructing a Minimum Spanning Tree after Deletion of Any Node
Authors:Das  Loui
Affiliation:Lucent Technologies, PO Box 7033, Naperville, IL 60566-7033, USA., US
Graduate College, University of Illinois at Urbana-Champaign, 202 Coble Hall, 801 S. Wright St., Champaign, IL 61820, USA., US
Abstract:Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log 2 n) time using m processors on a CREW PRAM.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号