Publication Type:

Journal Article

Authors:

Ganesan, A.

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

Keywords:

Algorithms, Cayley graphs, Diameter, Estimation, Forestry, Interconnection networks, Mathematics, Permutations, Polynomial approximation, Polynomial-time, Transposition trees, Trees, Trees (mathematics), Upper Bound

Abstract:

<p>A 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>

Notes:

cited By (since 1996)0

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.

207
PROGRAMS
OFFERED
5
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS