最小树的一般算法

本文根据设计并行算法的基本原则,给出了最小树的两个对偶定理.在此基础上,建立了两种对偶的同步并行算法的雏型.这两种算法恰恰在对偶的意义下,概括了以往的最小树算法.

General Algorithms for Finding Optimal Trees

In this paper, two daulity theorems on the optimal trees algorithms are given according to radical principles of structuring parallel algorithms. Then on the basis of the theorems, two daulity embryonic models of parallel algorithms are constructed. Finally it is shown that almost all well-known algorithms for finding optimal trees are exactly included in the two models of parallel algorithms.