Edge Update Algorithms for Minimum Spanning Forest on Reconfigurable Mesh
Wan Ying · Chinese Journal of Computers · 2000
The edge update of minimum spanning forest is very important in network routing and many other areas. Given an n vertex undirected weighted simple graph G , this paper proposes the following algorithms on 2D reconfigurable mesh of size n×n : determining the connectivity of an n vertex undirected graph in O (1) time and finding a path from a given vertex to the root of an n vertex directed tree in O (log n ) time, and proposes an algorithm for finding a path from a given vertex to the root of an n vertex directed tree in O (1)time on a 3D reconfigurable of size n×n×n . Based on these algorithms this paper proposes two parallel algorithms for the edge update of minimum spanning forest of G . One runs on an n×n 2D reconfigurable mesh with time complexity of O (log n ). The other runs on an n×n×n 3D reconfigurable mesh with time complexity of O (1).