Efficient Graph-Theoretic Algorithms on a Linear Array with a Reconfigurable Pipelined Bus System

We present efficient algorithms for solving several fundamental graph-theoretic problems on a Linear Array with a Reconfigurable Pipelined Bus System (LARPBS), one of the recently proposed models of computation based on optical buses. Our algorithms include finding connected components, minimum spanning forest, biconnected components, bridges and articulation points for an undirected graph. We compute the connected components and minimum spanning forest of a graph in O(log n) time using O(m+n) processors where m and n are the number of edges and vertices in the graph and m=O(n ²) for a dense graph. Both the processor and time complexities of these two algorithms match the complexities of algorithms on the Arbitrary and Priority CRCW PRAM models which are two of the strongest PRAM models. The algorithms for these two problems published by Li et al. [7] have been considered to be the most efficient on the LARPBS model till now. Their algorithm [7] for these two problems require O(log n) time and O(n ³/log n) processors. Hence, our algorithms have the same time complexity but require less processors. Our algorithms for computing biconnected components, bridges and articulation points of a graph run in O(log n) time on an LARPBS with O(n ²) processors. No previous algorithm was known for these latter problems on the LARPBS.     

基于生成树代价和和几何约束的文物碎片自动重组方法

在文物碎片自动重组过程中, 针对传统基于几何驱动重组的方法容易受噪声影响会产生误匹配等问题, 本文提出一种基于生成树代价和和几何约束的文物碎片自动重组方法. 首先, 采用曲度函数提取碎片断裂面上凹凸性显著的n个特征点; 进而, 对其进行拓扑重构, 以特征点空间位置之间的欧氏距离为权值, 构造n阶带权无向完全图及其最小、最大生成树, 以生成树的代价和为邻接约束, 快速筛选潜在匹配碎片; 然后, 再以特征点的主曲率构造特征串, 引入Hausdorff距离来衡量两个特征串之间的相似程度, 可以有效找出配对碎片; 最后, 采用四元数法估算旋转平移矩阵将碎片粗对齐, 再采用迭代最近点算法实现精确对齐. 实验结果表明, 重组误差小于1 mm, 与传统方法相比, 该方法特征点数量较少, 计算量小, 有效提高了碎片重组的效率和准确性.