Exact Analysis of Three Tree Contraction Algorithms
Exact Analysis of Three Tree Contraction Algorithms
复制标题
三种树收缩算法的精确分析
DOI：
10.1007/3-540-54458-5_81
复制
发表时间：
1991
期刊：
影响因子：
--
通讯作者：
Tomasz Szymacha
中科院分区：
文献类型：
--
作者：
Wojciech Plandowski;W. Rytter;Tomasz Szymacha
我们分析了三种基本树收缩算法的确切迭代次数。对于常数c，c′，这些数的界为c log 2（n）+ c′。我们证明了[10，11]中给出的两个树收缩算法在log 2（n）处的最佳常数系数是1/log 2 φ，其中φ是黄金分割比。φ = 1.618和1/log 2 φ = 1.44。对于米勒和Reif的耙压缩算法，最佳系数被示出为1/log 2 λ，其中λ是方程λ3= λ + 1的真实的解。λ = 1.32和1/log 2 λ = 2.46。因此，与米勒和Reif算法相比，[10，11]中的算法的迭代次数减少了大约两倍。虽然这三种算法都使用类似的操作，但它们的行为是不同的，必须单独分析。c的下界的证明相当简单，然而上界的证明（与下界匹配）则更为复杂。复杂递归方程（类似于动态规划递归）的解的一些有用性质需要大量的计算机实验来猜测。几种类型的Fibonacci树（Tk，Tk* 和Pk）在分析中起着重要的作用。有向无环图的收缩与树收缩类似地进行分析。我们在这里也有助于树的组合。
We analyze the exact numbers of iterations in three basic tree contraction algorithms. These numbers are bounded by c log2(n) + c′, for some constants c, c′. We show that the best constant coefficient at log2(n) for the two tree contraction algorithms given in [10, 11] is 1/log2φ, where φ is the golden ratio. φ ≈ 1.618 and 1/log2φ ≈ 1.44. For the rake-compress algorithm of Miller and Reif the best coefficient is shown to be 1/log2λ, where λ is a real solution of the equation λ3= λ + 1. λ ≈ 1.32 and 1/log2λ ≈ 2.46. Consequently, the algorithms from [10, 11] make about twice less iterations compared with the Miller and Reif algorithm. Although all three algorithms use similar operations their behaviours are different and they have to be analyzed separately. The proof of the lower bound for c is rather simple, however the proof of the upper bound (matching the lower bound) is more involved. It required a big number of computer experiments to guess some useful properties of the solutions of complicated recurrence equations (similar to dynamic programming recurrences). Several types of Fibonacci-like trees (Tk, Tk*and Pk) play an important role in the analysis. A contraction of directed acyclic graphs is analyzed similarly as tree-contraction. We contribute here also to the combinatorics of trees.