Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees

Details Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees

2000-02-08

arxiv.org/abs/cs/0002005v1

Computer Science

Distributed, Parallel, and Cluster Computing

32 pages, 4 figures

Scientific paper

In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights. The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time. The first part of the paper surveys various algorithms available today both in sequential and distributed environments to solve static MST problem. We also present some of the efficient sequential algorithms for computing dynamic MST like the Frederickson's algorithm and Eppstein's sparsification technique. Lastly we present our new sequential and distributed algorithms for dynamic MST problem. To our knowledge, this is the first of the distributed algorithms for computing dynamic MSTs.

Affiliated with

Also associated with

No associations

Rating

Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-558337