English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

A problem of practical and theoretical interest is to determine or estimatethe diameter of various families of Cayley networks. The previously knownestimate for the diameter of Cayley graphs generated by transposition trees isan 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 showthat for every $n$, there exists a tree on $n$ vertices, such that thedifference between the upper bound and the true diameter value is at least$n-4$.  Evaluating their upper bound takes time $\Omega(n!)$. In this paper, weprovide an algorithm that obtains an estimate of the diameter, but whichrequires only time $O(n^2)$; furthermore, the value obtained by our algorithmis less than or equal to the previously known diameter upper bound. Such animprovement to polynomial time, while still performing at least as well as theprevious bound, is possible because our algorithm works directly with thetransposition tree on $n$ vertices and does not require examining any of thepermutations. We also provide a tree for which the value computed by ouralgorithm is not necessarily unique, which is an important result because suchexamples 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 anupper bound on the diameter.

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