Back close

An efficient algorithm for the diameter of cayley graphs generated by transposition trees

Publication Type : Journal Article

Publisher : IAENG International Journal of Applied Mathematics

Source : IAENG International Journal of Applied Mathematics, Volume 42, Number 4, p.214-223 (2012)

Url : http://www.scopus.com/inward/record.url?eid=2-s2.0-84874642679&partnerID=40&md5=5443f14c90ef5c17763c3d4e3a6870d5

Campus : Coimbatore

School : School of Engineering

Department : Mathematics

Verified : Yes

Year : 2012

Abstract : pA problem of practical and theoretical interest is to determine or estimate the diameter of various families of Cayley networks. The previously known estimate for the diameter of Cayley graphs generated by transposition trees is an upper bound given in the oft-cited paper of Akers and Krishnamurthy (1989). In this work, we first assess the performance of their upper bound. We show that for every n, there exists a tree on n vertices, such that the difference between the upper bound and the true diameter value is at least n - 4. Evaluating their upper bound takes time Ω (n!). In this paper, we provide an algorithm that obtains an estimate of the diameter, but which requires only time O(n2); furthermore, the value obtained by our algorithm is less than or equal to the previously known diameter upper bound. Such an improvement to polynomial time, while still performing at least as well as the previous bound, is possible because our algorithm works directly with the transposition tree on n vertices and does not require examining any of the permutations. We also provide a tree for which the value computed by our algorithm is not necessarily unique, which is an important result because such examples are quite rare. For all families of trees we have investigated so far, each of the possible values computed by our algorithm happens to also be an upper bound on the diameter./p

Cite this Research Publication : A. Ganesan, “An efficient algorithm for the diameter of cayley graphs generated by transposition trees”, IAENG International Journal of Applied Mathematics, vol. 42, pp. 214-223, 2012.

Admissions Apply Now