1990/06/01 by Fred S. Annexstein, Marc Baumslag, Arnold L. Rosenberg · 211 citations
Computer Science · Engineering · Mathematics · #Cayley graph #Combinatorics #Discrete mathematics #Finite Group Theory Research #Graph #Interconnection Networks and Systems #Mathematics #Vertex (graph theory) #graph theory and CDMA systems
paper · doi:10.1137/0219037
published in SIAM Journal on Computing 19(3), 544-569 (Society for Industrial and Applied Mathematics)
openalex publication_date 1990/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
The authors develop an algebraic framework that exposes the structural kinship among the deBruijn, shuffle-exchange, butterfly, and cube-connected cycles networks and illustrate algorithmic benefits that ensue from the exposed relationships. The framework builds on two alge-braically specified genres of graphs: A group action graph (GAG, for short) is given by a set V of vertices and a set Π of permutations of V : For each v ∈ V and each π ∈ Π, there is an arc labeled π from vertex v to vertex v π. A Cayley graph is a GAG(V, Π), where V is the group \bf Gr(Π) generated by Π and where each π ∈ Π acts on each g ∈ \bf Gr (Π) by right multiplication. The graphs (\bf Gr(Π), Π) and (V, Π) are called associated graphs. It is shown that every GAG is a quotient graph of its associated Cayley graph. By applying such general results, the authors determine the following: • The butterfly network (a Cayley graph) and the deBruijn network (a GAG) are associated graphs. • The cube-connected cycles network (a Cayley graph) and the shuffle-exchange network (a GAG) are associated graphs. • The order-n instance of both the butterfly and the cube-connected cycles share the same underlying group, but have slightly different generator sets Π. By analyzing these algebraic results, it is delimited, for any Cayley graph G and associated GAG H, a family of “leveled” algorithms which run as efficiently on H as they do on (the much larger) G. Further analysis of the results yields new, surprisingly efficient simulations by the shuffle-oriented networks (the shuffle-exchange and deBruijn networks) of like-sized butterfly-oriented networks (the butterfly and cube-connected cycles networks): • An N-vertex butterfly-oriented network can be simulated by the smallest shuffle-oriented network that is big enough to hold it with slowdown O(log log N). This simulation is exponentially faster than the anticipated logarithmic slowdown. The mappings that underlie the simulation can be computed in linear time; and they afford one an algorithmic tech-nique for translating any program developed for a butterfly-oriented architecture into an equivalent program for a shuffle-oriented architecture, the latter program incurring only the indicated slowdown factor.