论文标题
一个用于计算最小跨越树的快速图形程序
A Fast Graph Program for Computing Minimum Spanning Trees
论文作者
论文摘要
当使用图形转换规则实现图形算法时，挑战是匹配传统语言中程序的效率。为了帮助克服这一挑战，图形编程语言gp 2具有根生根的规则，在轻度条件下，在有限度图上可以在恒定时间内匹配。在本文中，我们提出了一个有效的GP 2程序，用于计算最小跨越树。我们提供经验性绩效结果，作为该计划在有限程度图上的次级复杂性的证据。这是使用深度优先搜索以及扎根的图形变换来实现的。该程序基于Boruvka的算法，用于最小跨越树。我们的性能结果表明，该程序的时间复杂性与Boruvka算法的经典实现（即O（m log N）的经典实现相一致，其中m是边缘的数量，n是节点的数量。
When using graph transformation rules to implement graph algorithms, a challenge is to match the efficiency of programs in conventional languages. To help overcome that challenge, the graph programming language GP 2 features rooted rules which, under mild conditions, can match in constant time on bounded degree graphs. In this paper, we present an efficient GP 2 program for computing minimum spanning trees. We provide empirical performance results as evidence for the program's subquadratic complexity on bounded degree graphs. This is achieved using depth-first search as well as rooted graph transformation. The program is based on Boruvka's algorithm for minimum spanning trees. Our performance results show that the program's time complexity is consistent with that of classical implementations of Boruvka's algorithm, namely O(m log n), where m is the number of edges and n the number of nodes.
