×

Embedding circulant networks into butterfly and benes networks. (English) Zbl 1401.05100

Kratochvíl, Jan (ed.) et al., Combinatorial algorithms. 25th international workshop, IWOCA 2014, Duluth, MN, USA, October 15–17, 2014. Revised selected papers. Cham: Springer (ISBN 978-3-319-19314-4/pbk; 978-3-319-19315-1/ebook). Lecture Notes in Computer Science 8986, 298-306 (2015).
Summary: The dilation of an embedding is defined as the maximum distance between pairs of vertices of host graph that are images of adjacent vertices of guest graph. An embedding with a long dilation faces many problems, such as long communication delay, coupling problems and the existence of different types of uncontrolled noise. In this paper, we compute the minimum dilation of embedding circulant networks into butterfly and benes networks.
For the entire collection see [Zbl 1318.68027].

MSC:

05C12 Distance in graphs
05C82 Small world graphs, complex networks (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chaudhary, V., Aggarwal, J.K.: Generalized mapping of parallel algorithms onto parallel architectures. In: Proceeding of International Conference on Parallel Processing, pp. 137-141 (1990)
[2] Dvor̂ák, T., Dense sets and embedding binary trees into hypercubes, Discrete Appl. Math., 155, 4, 506-514 (2007) · Zbl 1111.05023 · doi:10.1016/j.dam.2006.09.003
[3] Bezrukov, S.L., Chavez, J.D., Harper, L.H., Röttger, M., Schroeder, U.P.: Embedding of hypercubes into grids. In: Mortar Fire Control System, pp.693-701 (1998)
[4] Rajasingh, I.; Rajan, B.; Rajan, RS, Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs, Int. J. Comput. Math., 89, 15, 1970-1978 (2012) · Zbl 1255.68040 · doi:10.1080/00207160.2012.697557
[5] Gupta, AK; Nelson, D.; Wang, H., Efficient embeddings of ternary trees into hypercubes, J. Parallel Distrib. Comput., 63, 6, 619-629 (2003) · Zbl 1035.68081 · doi:10.1016/S0743-7315(03)00037-6
[6] Bezrukov, SL, Embedding complete trees into the hypercube, Discrete Appl. Math., 110, 2-3, 101-119 (2001) · Zbl 0980.05022 · doi:10.1016/S0166-218X(00)00256-0
[7] Manuel, P.; Rajasingh, I.; Rajan, RS, Embedding variants of hypercubes with dilation 2, J. Interconnect. Netw., 13, 1-2, 1-16 (2012)
[8] Ramanathan, P.; Shin, KG, Reliable broadcast in hypercube multicomputers, IEEE Trans. Comput., 37, 12, 1654-1657 (1988) · doi:10.1109/12.9743
[9] Wong, GK; Coppersmith, DA, A combinatorial problem related to multimodule memory organization, J. Assoc. Comput. Mach., 21, 3, 392-401 (1994) · Zbl 0353.68039 · doi:10.1145/321832.321838
[10] Boesch, FT; Wang, J., Reliable circulant networks with minimum transmission delay, IEEE Trans. Circuit Syst., 32, 12, 1286-1291 (1985) · Zbl 0583.94018 · doi:10.1109/TCS.1985.1085667
[11] Bermond, JC; Comellas, F.; Hsu, DF, Distributed loop computer networks: a survey, Surv. J. Parallel Distrib. Comput., 24, 1, 2-10 (1995) · doi:10.1006/jpdc.1995.1002
[12] Beivide, R.; Herrada, E.; Balcazar, JL; Arruabarrena, A., Optimal distance networks of low degree for parallel computers, IEEE Trans. Comput., 40, 10, 1109-1124 (1991) · Zbl 1395.68024 · doi:10.1109/12.93744
[13] Wilkov, RS, Analysis and design of reliable computer networks, IEEE Trans. Commun., 20, 3, 660-678 (1972) · doi:10.1109/TCOM.1972.1091214
[14] Xu, JM, Topological Structure and Analysis of Interconnection Networks (2001), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1046.68026 · doi:10.1007/978-1-4757-3387-7
[15] Manuel, P.; Abd-El-Barra, MI; Rajasingh, I.; Rajan, B., An efficient representation of benes networks and its applications, J. Discrete Algorithms, 6, 1, 11-19 (2008) · Zbl 1159.05307 · doi:10.1016/j.jda.2006.08.003
[16] Garey, MR; Johnson, DS, Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), San Francisco: Freeman, San Francisco · Zbl 0411.68039
[17] Harper, LH, Global Methods for Combinatorial Isoperimetric Problems (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1043.05002 · doi:10.1017/CBO9780511616679
[18] Rajan, R.S., Miller, M., Rajasingh, I., Manuel, P.: Embedding circulant networks into certain trees. J. Comb. Optim. (submitted)
[19] Rajan, R.S., Manuel, P., Rajasingh, I., Parthiban, N., Miller, M.: A lower bound for dilation of an embedding. Comput. J. (2015). http://comjnl.oxfordjournals.org/content/early/2015/04/01/comjnl.bxv021
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.