Diameter Search Algorithms for Directed Cayley Graphs

Abstract

It is considered a well known diameter search problem for finite groups. It can be formulated as follows: find the maximum possible diameter of the group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph. In the paper a closely related problem is considered. For a specific system of generators find the diameter of corresponding Cayley graph. It is shown that the last problem is polynomially reduced to the problem of searching the minimal decomposition of elements over a system of generators. It is proposed five algorithms to solve the diameter search problem: simple down search algorithm, fast down search algorithm, middle down search algorithms, homogeneous down search algorithm and homogeneous middle down search algorithm.

Locations

• Mohyla Mathematical Journal - View - PDF