[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Greedy Routing in Circulant Networks

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Data Availability

Not applicable.

Code Availability

For the computational results summarized in Tables 1, 2, 3 and 4, the authors have created some standalone functions in the language R, in conjunction with the igraph library. These functions are not completely automated, and they are not organized as a package, but they can still be made available to other researchers upon request.

Notes

  1. We have modified the original formulation of these families slightly.

  2. Also called normal, or totally orderly.

References

  1. Adamaszek, A., Adamaszek, M.: Combinatorics of the change-making problem. Eur. J. Combin. 31, 47–63 (2010)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  3. Boesch, F.T., Wang, J.F.: Reliable circulant networks with minimal transmission delay. IEEE Trans. Circ. Syst. 32, 1286–1291 (1985)

    Article  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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

  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

  10. Gómez, D., Gutiérrez, J., Ibeas, A.: Optimal routing in double loop networks. Theoret. Comput. Sci. 381, 68–85 (2007)

    Article  MathSciNet  Google Scholar 

  11. Hafner, P.R.: Large Cayley graphs and digraphs with small degree and diameter. Research Report CDMTCS-005, University of Auckland, New Zealand (1995)

  12. Hwang, F.K.: A survey on multi-loop networks. Theoret. Comput. Sci. 299, 107–121 (2003)

    Article  MathSciNet  Google Scholar 

  13. Lewis, R.: The degree-diameter problem for circulant graphs of degree 8 and 9. Electron. J. Combin. 21, 4 (2014)

    Article  MathSciNet  Google Scholar 

  14. Lewis, R.: The degree-diameter problem for circulant graphs of degree 10 and 11. Discret. Math. 341, 2553–2566 (2018)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  20. Monakhova, E.A.: A survey on undirected circulant graphs. Discret. Math. Algorithms Appl. 4, 1 (2012)

    Article  MathSciNet  Google Scholar 

  21. Monakhova, E.A., Romanov, AYu., Lezhnev, E.V.: Shortest path search algorithm in optimal two-dimensional circulant networks: implementation for networks-on-chip. IEEE Access 20, 20 (2020)

    Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  26. Shallit, J.: What this country needs is an 18c piece. Math. Intell. 25(2), 20–23 (2003)

    Article  Google Scholar 

  27. Sulanke, R.: Objects counted by the central Delannoy numbers. J. Integer Sequences 6, Art. 03.1.5 (2003)

    MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  31. Vassilev-Missana, M.V., Atanassov, K.T.: On Delanoy [sic] numbers. Annuaire Univ. Sofia Fac. Math. Inform. 81, 153–162 (1987)

    MathSciNet  MATH  Google Scholar 

  32. Vetrík, T.: Cayley graphs of given degree and diameters 3, 4 and 5. Discret. Math. 313, 213–216 (2013)

    Article  MathSciNet  Google Scholar 

  33. Wong, C.K., Coppersmith, D.: A combinatorial problem related to multimodule memory organizations. J. ACM 21, 392–402 (1974)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We wish to thank the anonymous referee, whose suggestions have helped us improve the paper.

Funding

The authors have not disclosed any funding.

Author information

Authors and Affiliations

  1. Department of Computer Science and Mathematics, Universitat Rovira i Virgili, Tarragona, Spain

    Hebert Pérez-Rosés, Maria Bras-Amorós & José Miguel Serradilla-Merinero

  2. Conjoint Fellow, University of Newcastle, Newcastle, Australia

    Hebert Pérez-Rosés

Authors
  1. Hebert Pérez-Rosés
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maria Bras-Amorós
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. José Miguel Serradilla-Merinero
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Not applicable.

Corresponding author

Correspondence to Hebert Pérez-Rosés.

Ethics declarations

Conflicts of interest

The authors have not disclosed any competing interests.

Human and animal rights

Not applicable.

Ethics approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix: Tables of Large Greedy Circulant Graphs and Digraphs

Appendix: Tables of Large Greedy Circulant Graphs and Digraphs

See Tables 1, 2, 3 and 4.

Table 1 Largest circulant digraphs derived from the Fibonacci sequence (the degree is the length of the sequence prefix)
Full size table
Table 2 Largest circulant graphs derived from the Fibonacci sequence (the degree is the length of the sequence prefix)
Full size table
Table 3 Some large greedy circulant digraphs
Full size table
Table 4 Some large greedy circulant graphs
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Pérez-Rosés, H., Bras-Amorós, M. & Serradilla-Merinero, J.M. Greedy Routing in Circulant Networks. Graphs and Combinatorics 38, 86 (2022). https://doi.org/10.1007/s00373-022-02489-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-022-02489-9

Keywords

Mathematics Subject Classification

Search

Navigation