Group Action Graphs and Parallel Architectures

DOI10.1137/0219037zbMath0698.68064OpenAlexW2146796596MaRDI QIDQ3476285

Fred S. Annexstein, Arnold L. Rosenberg, Marc Baumslag

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219037

zbMATH Keywords

Cayley graphnetwork simulationbutterfly networkinterconnection networkgraph embeddingde Bruijn networkparallel architecturesgroup action graphcube-connected cycles networksshiffle-exchange network

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15) Theory of software (68N99)

Related Items (52)

Biswapped networks: a family of interconnection architectures with advantages over swapped or OTIS networks ⋮ Two edge-disjoint hamiltonian cycles in the butterfly graph ⋮ Action graph of a semigroup act & its functorial connection ⋮ Containment of butterflies in networks constructed by the line digraph operation ⋮ On the diameter and bisector size of Cayley graphs ⋮ Broadcasting in butterfly and deBruijn networks ⋮ Towards worst-case churn resistant peer-to-peer systems ⋮ Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes ⋮ An algebraic analysis of the connectivity of De Bruijn and shuffle- exchange digraphs ⋮ Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes ⋮ Unnamed Item ⋮ Absorption Cayley graph ⋮ Two-sided Group Digraphs and Graphs ⋮ A new digraphs composition with applications to de Bruijn and generalized de Bruijn digraphs ⋮ On quasi-Cayley graphs ⋮ FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR ⋮ Unnamed Item ⋮ Hamiltonian cycles and paths in Cayley graphs and digraphs---a survey ⋮ The shuffle exchange network has a Hamiltonian path ⋮ Labelings in Cayley digraphs ⋮ Broadcasting in butterfly and debruijn networks ⋮ Cycles in butterfly graphs ⋮ Cycles in the cube-connected cycles graph ⋮ Gossiping and routing in second-kind Frobenius graphs ⋮ Cycles in cube-connected cycles graphs ⋮ Minimum spanners of butterfly graphs ⋮ Algebraic specification of interconnection network relationships by permutation voltage graph mappings ⋮ The shuffle exchange network has a Hamiltonian path ⋮ Broadcasting in the butterfly network ⋮ Structural properties of Cayley digraphs with applications to mesh and pruned torus interconnection networks ⋮ Group graphs and computational symmetry on massively parallel architecture ⋮ A note on recursive properties of the de Bruijn, Kautz and FFT digraphs ⋮ Connectedness of two-sided group digraphs and graphs ⋮ New methods for using Cayley graphs in interconnection networks ⋮ Product-shuffle networks: Toward reconciling shuffles and butterflies ⋮ Large butterfly Cayley graphs and digraphs ⋮ On the pagenumber of trivalent Cayley graphs ⋮ On routing and diameter of metacyclic graphs ⋮ Fully symmetric swapped networks based on bipartite cluster connectivity ⋮ A unified framework for off-line permutation routing in parallel networks ⋮ The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing ⋮ Rotational circulant graphs ⋮ Exposing graph uniformities via algebraic specification ⋮ Bounded budget connection (BBC) games or how to make friends and influence people, on a budget ⋮ Derangement action digraphs and graphs ⋮ Cayley graphs as classifiers for data mining: the influence of asymmetries ⋮ Self-spanner graphs ⋮ Cayley graphs as models of deterministic small-world networks ⋮ Characteristic polynomials of digraphs having a semi-free action ⋮ On the Strictness of a Bound for the Diameter of Cayley Graphs Generated by Transposition Trees ⋮ Factorization of de Bruijn digraphs by cycle-rooted trees ⋮ A note on cyclic-cubes

This page was built for publication: Group Action Graphs and Parallel Architectures