可重构造网孔机器上最小生成森林的边更新算法

Edge Update Algorithms for Minimum Spanning Forest on Reconfigurable Mesh

最小生成森林的边更新在网络路由等方面有着重要的应用价值 .给定 n个结点的无向加权单图 G,该文首先在 n× n的二维可重构造网孔机器上提出了在 O(1)时间内判断 n个结点的无向图的连通性和在 O(logn)时间内求 n个结点的内向树中任一结点到根的路径两个算法 ,并在 n× n× n的三维可重构造网孔机器上提出了 O(1)时间内求 n个结点内向树中任一结点到根的路径的算法 .然后在上述算法的基础上提出了两个 G的最小生成森林的边更新算法 ,一个运行在 n× n的二维可重构造网孔机器上 ,时间复杂度是 O(logn) ,另一个运行在 n× n× n的三维可重构造网孔机器上 ,时间复杂度是 O(1) .

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).