2002 | OriginalPaper | Buchkapitel
Comparing Star and Pancake Networks
verfasst von : Linda Morales, I. Hal Sudborough
Erschienen in: The Essence of Computation
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Low dilation embeddings are used to compare similarities between star and pancake networks. The pancake network of dimension n, Pn, has n! nodes, one for each permutation, and an undirected edge between permutations (nodes) when some prefix reversal transforms one permutation into the other. The star network of dimension n, Sn, has n! nodes, one for each permutation, and an undirected edge between permutations (nodes) when the exchange of the first element with some other element transforms one permutation into the other. Comparisons with the burnt pancake network are also discussed. The burnt pancake network, BPn, has 2n.n! nodes, one for each signed permutation, and an undirected edge between signed permutations (nodes) when some prefix reversal transforms one signed permutation into the other, and all symbols in the reversed prefix change sign. Some of the embeddings shown are: $$ \begin{gathered} \bullet P_n \mathop \Rightarrow \limits^{dil 1} S_{2n} , \bullet S_n \mathop \Rightarrow \limits^{dil 1} P_{(n^3 - 4n^2 + 5n + 4)/2} \hfill \\ \bullet BP_n \mathop \Rightarrow \limits^{dil 1} S_{2n} , \bullet S_n \mathop \Rightarrow \limits^{dil 2} P_{2n - 2} \hfill \\ \end{gathered} $$