Greedy routing in circulant networks. (English) Zbl 1486.05291
Summary: We address the problem of constructing large circulant networks with given degree and diameter, and efficient routing schemes. First we discuss the theoretical upper bounds and their asymptotics. Then we apply concepts and tools from the change-making problem to efficient routing in circulant graphs. With these tools we investigate some of the families of circulant graphs that have been proposed in the literature, and we construct tables of large circulant graphs and digraphs with efficient routing properties.
MSC:
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C35 | Extremal problems in graph theory |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
network design; degree/diameter problem; circulant graphs; network routing; greedy algorithmSoftware:
OEISReferences:
| [1] | Adamaszek, A.; Adamaszek, M., Combinatorics of the change-making problem, Eur. J. Combin., 31, 47-63 (2010) · Zbl 1178.90281 · doi:10.1016/j.ejc.2009.05.002 |
| [2] | Branković, L.; Miller, M.; Plesník, J.; Ryan, J.; Širán, J., A note on constructing large Cayley graphs of given degree and diameter by voltage assignments, Electron. J. Combin., 5, R9 (1998) · Zbl 0885.05071 · doi:10.37236/1347 |
| [3] | Boesch, FT; Wang, JF, Reliable circulant networks with minimal transmission delay, IEEE Trans. Circ. Syst., 32, 1286-1291 (1985) · Zbl 0583.94018 · doi:10.1109/TCS.1985.1085667 |
| [4] | Cai, X.: Canonical coin systems for change-making problems. In: Proceedings of the 9th IEEE International Conference on Hybrid Intelligent Systems, pp. 499-504 (2009) |
| [5] | Chang, H.-W., Chen, S.-Y.: New families of triple-loop networks. In: Proceedings of the 2004 IEEE Asia-Pacific Conference on Circuits and Systems, pp. 893-896 (2004) |
| [6] | Dougherty, R.; Faber, V., The degree diameter problem for several varieties of Cayley graphs I: the Abelian case, SIAM J. Discret. Math., 17, 3, 478-519 (2004) · Zbl 1056.05046 · doi:10.1137/S0895480100372899 |
| [7] | Elspas, B.: Topological constraints on interconnection-limited logic. In: Proceedings the 5th Annual IEEE Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, USA, pp. 133-137 (1964) |
| [8] | Feria-Puron, R., Pérez-Rosés, H., Ryan, J.: Searching for large circulant graphs. arXiv:1503.07357v1 · Zbl 1338.05252 |
| [9] | Giakkoupis, G., Hadzilacos, V.: On the complexity of greedy routing in ring-based peer-to-peer networks. In: Proceedings of PODC 2007, pp. 99-108 · Zbl 1283.68070 |
| [10] | Gómez, D.; Gutiérrez, J.; Ibeas, A., Optimal routing in double loop networks, Theoret. Comput. Sci., 381, 68-85 (2007) · Zbl 1188.68213 · doi:10.1016/j.tcs.2007.04.002 |
| [11] | Hafner, P.R.: Large Cayley graphs and digraphs with small degree and diameter. Research Report CDMTCS-005, University of Auckland, New Zealand (1995) · Zbl 0830.05025 |
| [12] | Hwang, FK, A survey on multi-loop networks, Theoret. Comput. Sci., 299, 107-121 (2003) · Zbl 1038.68004 · doi:10.1016/S0304-3975(01)00341-3 |
| [13] | Lewis, R., The degree-diameter problem for circulant graphs of degree 8 and 9, Electron. J. Combin., 21, 4 (2014) · Zbl 1305.05107 · doi:10.37236/4279 |
| [14] | Lewis, R., The degree-diameter problem for circulant graphs of degree 10 and 11, Discret. Math., 341, 2553-2566 (2018) · Zbl 1392.05027 · doi:10.1016/j.disc.2018.05.024 |
| [15] | López, N.; Pérez-Rosés, H.; Pujolàs, J., The degree/diameter problem for mixed abelian Cayley graphs, Discret. Appl. Math., 231, 190-197 (2017) · Zbl 1369.05106 · doi:10.1016/j.dam.2017.04.018 |
| [16] | Machbeth, H.; Šiagiová, J.; Širáň, J.; Vetrík, T., Large Cayley graphs and vertex-transitive non-Cayley graphs of given degree and diameter, J. Graph Theory, 64, 87-98 (2009) · Zbl 1230.05158 |
| [17] | Martínez, C., Beivide, R., Izu, C., Alonso, J.M.: Characterization of the class of optimal dense circulant graphs of degree four. In: Proceedings of the XIV Jornadas de Paralelismo, Leganés, Madrid, Spain (2003) |
| [18] | Miller, M.; Pérez-Rosés, H.; Ryan, J., The maximum degree and diameter-bounded subgraph in the mesh, Discret. Appl. Math., 160, 1782-1790 (2012) · Zbl 1245.05023 · doi:10.1016/j.dam.2012.03.035 |
| [19] | Miller, M.; Širáň, J., Moore graphs and beyond: a survey of the degree-diameter problem, Electron. J. Combin. Dyn. Surv., 14, 1-61 (2013) · Zbl 1079.05043 |
| [20] | Monakhova, EA, A survey on undirected circulant graphs, Discret. Math. Algorithms Appl., 4, 1 (2012) · Zbl 1247.05115 · doi:10.1142/S1793830912500024 |
| [21] | Monakhova, EA; Romanov, AYu; Lezhnev, EV, Shortest path search algorithm in optimal two-dimensional circulant networks: implementation for networks-on-chip, IEEE Access, 20, 20 (2020) |
| [22] | Muga, F.P., II.: Undirected circulant graphs. In: Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN), pp. 113-118 (1994) |
| [23] | Muzychuk, M., A solution of the isomorphism problem for circulant graphs, Proc. Lond. Math. Soc., 3, 88, 1-41 (2004) · Zbl 1045.05052 · doi:10.1112/S0024611503014412 |
| [24] | OEIS: The On-Line Encyclopedia of Integer Sequences. http://oeis.org/classic/index.html |
| [25] | Pearson, D., A polynomial-time algorithm for the change-making problem, Oper. Res. Lett., 33, 231-234 (2005) · Zbl 1177.90350 · doi:10.1016/j.orl.2004.06.001 |
| [26] | Shallit, J., What this country needs is an 18c piece, Math. Intell., 25, 2, 20-23 (2003) · doi:10.1007/BF02984830 |
| [27] | Sulanke, R., Objects counted by the central Delannoy numbers, J. Integer Sequences, 6, Art. 03.1.5 (2003) · Zbl 1012.05008 |
| [28] | The Degree \(/\) Diameter Problem. http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem |
| [29] | The Degree \(/\) Diameter Problem For Circulant Graphs. http://combinatoricswiki.org/wiki/The_Degree_Diameter_Problem_for_Circulant_Graphs |
| [30] | Thomson, A.; Zhou, S., Gossiping and routing in undirected triple-loop networks, Networks, 55, 4, 341-349 (2010) · Zbl 1202.90045 · doi:10.1002/net.20327 |
| [31] | Vassilev-Missana, MV; Atanassov, KT, On Delanoy [sic] numbers, Annuaire Univ. Sofia Fac. Math. Inform., 81, 153-162 (1987) · Zbl 0813.05005 |
| [32] | Vetrík, T., Cayley graphs of given degree and diameters 3, 4 and 5, Discret. Math., 313, 213-216 (2013) · Zbl 1257.05062 · doi:10.1016/j.disc.2012.10.006 |
| [33] | Wong, CK; Coppersmith, D., A combinatorial problem related to multimodule memory organizations, J. ACM, 21, 392-402 (1974) · Zbl 0353.68039 · doi:10.1145/321832.321838 |
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.
