×

Hypercube emulation of interconnection networks topologies. (English) Zbl 1348.05057

Summary: We address various topologies (de Bruijn, chordal ring, generalized Petersen, and meshes) in various ways (isometric embedding, embedding up to scale, and embedding up to a distance) in a hypercube or a half-hypercube. Example of obtained embeddings: infinite series of hypercube embeddable bubble sort and double chordal rings topologies, as well as of regular maps.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C65 Hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Danny Hillis, The Connection Machine,(MIT Press Series in Artificial Intelligence) (1986)
[2] Subercaze, On Metric Embedding for Boosting Semantic Similarity Computations (2015)
[3] Deza, Scale-isometric Polytopal Graphs in Hypercubes and Cubic Lattices (2004) · Zbl 1054.52007
[4] Brouwer, Distance-regular Graphs (1989) · Zbl 0747.05073
[5] Tylkin, On Hamming geometry of unitary cubes, Soviet Physics. Doklady 5 pp 40– (1960)
[6] Avis, Hypermetrie spaces and the Hamming cone, Canadian Journal of Mathematics 33 pp 795– (1981) · Zbl 0445.52008
[7] Deza, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15 (1997) · Zbl 1210.52001
[8] Kotsis G Interconnection topologies and routing for parallel processing systems ACPC Technical Reports Series
[9] Heydemann, ’Graph symmetry: algebraic methods and applications’ (1997)
[10] Deza, Recognition of the l1-graphs with complexity O(nm) and football in hypercube, in Special Issue Discrete Metric Spaces, European Journal of Combinatorics 17 pp 279– (1996) · Zbl 0854.05093
[11] Roussopoulos, A max{m,n} algorithm for determining the graph H from its line graph G, Information Processing Letters 2 pp 108– (1973) · Zbl 0274.05116
[12] Andoni A Deza M Gupta A Indyk P Raskhodnikova S Lower bounds for embedding edit distance into normed spaces, Proceedings of SODA’03 ACM-SIAM Symposium on Discrete Algorithms Baltimore 2003 · Zbl 1092.68685
[13] Matouśek J Open problems on embeddings of finite metric spaces 2011 http://kam.mff.cuni.cz/matousek/metrop.ps
[14] Koolen J On metric properties of regular graphs Master’s thesis Technische Universiteit Eindhoven 1990
[15] Preparata, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM 24 (5) pp 300– (1981)
[16] West, 2nd ed, in: Introduction to Graph Theory (2000)
[17] Klavzar, Structure of Fibonacci cubes: a survey, IMFM preprint series (Ljubljana, Slovenia: Institute of Mathematics, Physics and Mechanics 49 pp 1150– (2011)
[18] Deza, Hypercube embeddings of Wythoffians, Ars Mathematica Contemporanea 1 pp 99– (2008) · Zbl 1152.52005
[19] Gates, Bounds for sorting by prefix reversal, Discrete Mathematics pp 47– (1979) · Zbl 0397.68062
[20] Conder, Determination of all regular maps of small genus, Journal of Combinatorial Theory, Series B 81 pp 224– (2001) · Zbl 1028.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.