MOD-CHAR: an implementation of Char´s spanning tree enumeration algorithm and its complexity analysis

Two complexity analyses of MOD-CHAR are presented. It is shown that MOD-CHAR leads to better complexity results for J.P. Char´s algorithm than what could be obtained using the straightforward implementation implied in Char´s original presentation (see IEEE Trans. Circuit Theory, Vol.15, p.228-38, 1968). The class of graphs for which MOD-CHAR and, hence, Char´s algorithm, has linear time complexity per spanning tree generated is identified. This class is more general than the corresponding one identified in R. Jayakumar et al. (see ibid., vol.31, no.10, p.853-60, 1984). Using a result on random graphs, it is proved that for almost all graphs MOD-CHAR has linear worst-case time complexity per spanning tree generated. It is also shown that for any complete graph MOD-CHAR requires, on the average, at most seven computational steps to generate a spanning tree. This result and computational experiences provide evidence to believe that for dense graphs of any order the time complexity of MOD-CHAR is O(t), where t is the number of spanning trees generated. On the other hand, there is enough evidence to conclude that for sparse graphs, Char´s original implementation is superior to MOD-CHAR