Algorithms for the degree-constrained minimum spanning tree and the hierarchical clustering problems using the nearest-neighbor techniques
Li-Jen Mao, Sheau-Dong Lang, Narsingh Deo · Journal of International Crisis and Risk Communication Research · 1999
In this dissertation, we explore the properties related to the nearest neighbor (NN) technique in the contexts of clustering methods and the minimum spanning trees. We present new algorithms that apply the NN technique to solving two classes of problems: the Degree-Constrained MST problem (d-MST) and the hierarchical agglomerative clustering problem. We perform a theoretical analysis of time complexity of the sequential and parallel implementations of our algorithms. We also present empirical results that validate our analysis. The main contributions of this research are as follows: (1) Design and analyze new hierarchical agglomerative clustering algorithms by applying the NN techniques. (a) Design the Diam-SLINK and the Radius-SLINK algorithms which improve the clustering performance of the single link method by avoiding the chaining effect in the clustering results, while maintaining the good time-efficiency of the single link method. (b) Implement and analyze the O( n)-space RNN-CLINK algorithm, providing both theoretical and empirical evidence that demonstrates average running time is O( n2 log n). (2) Explore the implementation of approximate algorithms for the d-MST problem and other constrained spanning tree problems. Specifically, we developed the following new parallel algorithms for d-MST based on the Tree-Construction (TC) approach: (a) The TC-RNN algorithm. Our experimental results based on extensive testing demonstrate that TC-RNN consistently finds spanning tree with the lower weight than that obtained from an existing d-MST algorithm using the iterative refinement (IR) approach. The TC-RNN algorithm finds a feasible solution in most cases even when d is as small as 2, but at the expense of greater execution time. (b) The TC-NNC algorithm. The execution time of TC-NNC is shorter than that of TC-RNN, and is very close to that of IR. The quality of solutions of TC-NNC is better than that of IR and is very close to that of TC-RNN.