论文标题
用于跨越树模量的精确算术算法
An exact-arithmetic algorithm for spanning tree modulus
论文作者
论文摘要
跨越树模量是有效抗性的概括，该抗性与图形强度和分数均匀性密切相关。已知与跨越树模量相关的最佳边缘密度可产生两个基于强度的任意图的分层分解，另一个是基于支子。在这里，我们介绍了一种用于跨越树模量的精确算术算法和使用坎宁安的算法用于图形漏洞的基于强度的分解。该算法利用了跨越漏洞问题的跨越树模量与关键边缘设置之间的有趣连接。本文介绍了新算法，描述了一种使用整数算术实现它的实用方法，并提供了一些示例和计算时间缩放测试。
Spanning tree modulus is a generalization of effective resistance that is closely related to graph strength and fractional arboricity. The optimal edge density associated with spanning tree modulus is known to produce two hierarchical decompositions of arbitrary graphs, one based on strength and the other on arboricity. Here we introduce an exact-arithmetic algorithm for spanning tree modulus and the strength-based decomposition using Cunningham's algorithm for graph vulnerability. The algorithm exploits an interesting connection between spanning tree modulus and critical edge sets from the vulnerability problem. This paper introduces the new algorithm, describes a practical means for implementing it using integer arithmetic, and presents some examples and computational time scaling tests.
