La computación de los caminos más cortos en grafos de Cayley

Question

Estoy interesado en los caminos más cortos en el grafo de Cayley de la alternancia grupo $A_{12}$ que actúa sobre los vértices del icosaedro, donde los generadores están dadas por 5 ciclos en los vecinos de un determinado vértice.

Hay una decente algoritmo para el cálculo de los caminos más cortos en un altamente simétrica de la gráfica, dada una lista explícita de los generadores? La fuerza bruta es factible, ya que hay sólo $12!/2$ diferentes elementos, pero sería bueno tener un algoritmo más rápido, si está disponible.

De fondo: Si el lugar 12 de la unidad de las esferas en torno a una unidad central de esfera en 3D en una estructura icosaédrica de configuración, cada generador puede ser realizada sin intersecciones o pérdida de contacto con la mudanza de los 5 a los vecinos de una cubierta exterior de la esfera P hacia P hacia adentro y girar alrededor de ellos. http://en.wikipedia.org/wiki/Kissing_number#cite_note-1

Answer 1

Deje $G$ ser un grupo finito y $A \subset G$ un conjunto de generadores cerrado bajo de inversión. Dado $g \in G$, buscamos a un mínimo la longitud de la secuencia $$g = a_1 \cdots a_k.$$ Una secuencia de longitud $k$ existe iff $\exists a_1 \cdots a_k = g$ fib $\exists a_1 \cdots a_{\lfloor k/2 \rfloor} = g a_1 \cdots a_{\lceil k/2 \rceil}$ fib $\exists a_L \in A^{\lfloor k/2 \rfloor}, a_R \in A^{\lceil k/2 \rceil}$ s.t. $a_L = g a_R$ fib $A^{\lfloor k/2 \rfloor} \cap g A^{\lceil k/2 \rceil} \ne \emptyset$.

Si $|A^k|$ es exponencial en $k$ hasta cerca del diámetro de $G$, esto es un ahorro sustancial con respecto a la fuerza bruta (algo parecido a $O(\sqrt{|G|})$ dependiendo de la estructura de $G$).