MOD—CHAR:Char的生成树枚举算法的实现和复杂性分析

• 作 者: R.Jaykumar K.Thulasiraman M.N.S.Swamy 李卫国
• 出 处: 长沙水电师院学报(自然科学版)
• 发表日期: 1989年06期
• 关键词: 生成树 枚举算法 CHAR MOD 复杂性分析 线性时间 子图 矩阵理论 图论 电路问题

本文提出了一种称之为MOD—CHAR的生成树枚举算法的实现方法和两种复杂性分析。它显示出MOD—CHAR方法比直接采用Char的原始形式所得到的算法的复杂性更低。对于几乎所有的图,MOD—CHAR方法均被证明在生成每个生成树时都只有线性的错误耗费时间。它也被显示对于任何一个完全图MOD—CHAR仅需要最多七个计算步骤来生成一个生成树。

This paper presents a method and two kinds of complexity analysis of the spanning tree enumeration algorithm called MOD-CHAR. It shows that the MOD-CHAR method is less complex than the algorithm that takes the original form of Char directly. For almost all graphs, the MOD-CHAR method has proved to be time consuming only with linear errors when generating each spanning tree. It is also shown that for any complete graph MOD-CHAR only a maximum of seven calculation steps are required to generate a spanning tree.