Structural and communicative properties of circulant networks

E. A. Monakhova

Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 92-115.

Résumé

Circulant graphs have been extensively investigated over the past 30 years and have the broad application to different fields of computer science and discrete mathematics. Two surveys on circulant networks have been published in English: by Bermond, Comellas and Hsu (1995) and by Hwang (2003). In Russian, a survey on circulant networks is presented in a book of Monakhov and Monakhova (2000). The present paper includes the results which have not been presented in these works, and also some new results in the area of undirected circulant networks research obtained during the last years.

Détail

Keywords: interconnection networks, circulant graphs, diameter, routing, broadcasting and gossiping.

Bibliographie

[1] Artamonov G. T., Topologiya regulyarnykh vychislitelnykh setei i sred, Radio i svyaz, M., 1985, 192 pp. | MR | Zbl

[2] Artamonov G. T., Tyurin V. D., Topologiya setei EVM i mnogoprotsessornykh sistem, Radio i svyaz, M., 1991, 248 pp.

[3] Vorobev V. A., “Prosteishie struktury odnorodnykh vychislitelnykh sistem”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 60, Novosibirsk, 1974, 35–49

[4] Vorobev V. A., Korneev V. V., “Nekotorye voprosy teorii struktur odnorodnykh vychislitelnykh sistem”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 60, Novosibirsk, 1974, 3–16

[5] Dimitriev Yu. K., “Analiz samodiagnosticheskikh svoistv struktur raspredelennykh zhivuchikh vychislitelnykh sistem”, Avtometriya, 1996, no. 5, 71–84

[6] Evdokimov S. A., Ponomarenko I. N., “Raspoznavanie i proverka izomorfizma tsirkulyantnykh grafov za polinomialnoe vremya”, Algebra i analiz, 15:6 (2003), 1–34 | MR | Zbl

[7] Evreinov E. V., Khoroshevskii V. G., Odnorodnye vychislitelnye sistemy, Nauka, Novosibirsk, 1978, 318 pp. | Zbl

[8] Kleinrok L., Kommunikatsionnye seti. Stokhasticheskie potoki i zaderzhki soobschenii, Nauka, M., 1970, 256 pp.

[9] Korneev V. V., “O makrostrukture odnorodnykh vychislitelnykh sistem”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 60, Novosibirsk, 1974, 17–34 | Zbl

[10] Korneev V. V., Parallelnye vychislitelnye sistemy, Nolidzh, M., 1999, 320 pp.

[11] Martines K., Stafford E., Baivide R., Gabidulin E. M., “Predstavlenie geksagonalnykh sozvezdii s pomoschyu grafov Eizenshteina–Yakobi”, Problemy peredachi informatsii, 44:1 (2008), 3–14 | MR | Zbl

[12] Monakhov O. G., “Parametricheskoe opisanie struktur odnorodnykh vychislitelnykh sistem”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 80, Novosibirsk, 1979, 3–17 | MR | Zbl

[13] Monakhov O. G., “Evolyutsionnyi sintez algoritmov na osnove shablonov”, Avtometriya (Novosibirsk), 42:1 (2006), 116–126 | MR

[14] Monakhova E. A., “Sintez optimalnykh diofantovykh struktur”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 80, Novosibirsk, 1979, 18–35 | MR | Zbl

[15] Monakhova E. A., “Ob analiticheskom opisanii optimalnykh dvumernykh diofantovykh struktur odnorodnykh vychislitelnykh sistem”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 90, Novosibirsk, 1981, 81–91 | MR | Zbl

[16] Monakhova E. A., “Algoritmy mezhmashinnykh vzaimodeistvii i rekonfiguratsii grafov svyazei v vychislitelnykh sistemakh s programmiruemoi strukturoi”, Vychislitelnye sistemy. Voprosy teorii i postroeniya VS, 94, Novosibirsk, 1982, 81–102 | MR | Zbl

[17] Monakhova E. A., “Optimalnye KAIS-struktury odnorodnykh vychislitelnykh sistem”, Elektronnoe modelirovanie, 1985, no. 3, 30–34

[18] Monakhova E. A., “Trekhmernye tsirkulyantnye seti svyazi parallelnykh vychislitelnykh sistem”, Avtometriya, 2006, no. 3, 106–118

[19] Monakhova E. A., “Multiplikativnye tsirkulyantnye seti”, Diskret. analiz i issled. oper., 17:5 (2010), 56–66 | MR

[20] Monakhova E. A., “Ob odnom ekstremalnom semeistve tsirkulyantnykh setei”, Diskret. analiz i issled. oper., 18:1 (2011), 77–84 | MR

[21] Monakhov O. G., Monakhova E. A., Parallelnye sistemy s raspredelennoi pamyatyu: struktury i organizatsiya vzaimodeistvii, Izd-vo SO RAN, Novosibirsk, 2000, 242 pp.

[22] Monakhov O. G., Monakhova E. A., “Sintez novykh semeistv optimalnykh regulyarnykh setei na osnove evolyutsionnykh vychislenii i templeitov funktsii”, Avtometriya, 2004, no. 4, 106–116

[23] Nesterenko B. B., Novotarskii M. A., “Kletochnye neironnye seti na tsirkulyantnykh grafakh”, Iskusstvennyi intellekt, 2009, no. 3, 132–138

[24] Trufanov S. V., “Nekotorye zadachi o rasstoyaniyakh na grafe”, Izv. AN SSSR. Tekhn. kibernetika, 1967, no. 3, 61–66 | MR | Zbl

[25] Yablonskii S. V., “Algoritm postroeniya vychislitelnykh setei s minimalnym srednim rasstoyaniem mezhdu uzlami”, Tez. dokl. Vses. sovesch. “Metody i programmy resheniya optimizatsionnykh zadach na grafakh i setyakh”, Novosibirsk, 1980, 103–105

[26] Ádám A., “Research problem 2–10”, J. Combin. Theory, 2 (1967), 393 | DOI

[27] Aguilo F., Fiol M. A., Garcia C., “Triple Loop Networks with Small Transmission Delay”, Discrete Math., 167–168 (1997), 3–16 | DOI | MR | Zbl

[28] Arden B. W., Lee H., “Analysis of chordal ring networks”, IEEE Trans. Computers, C-30 (1981), 291–295 | DOI | MR

[29] Balaban A. T., “Reaction graphs”, Graph Theoretical Approaches to Chemical Reactivity, eds. D. Bonchev, O. Mekenyan, Kluwer Academic Publishers, Netherlands, 1994, 137–180

[30] Barriere L., Fabrega J., Simo E., Zaragoza M., “Fault-Tolerant Routings in Chordal Ring Networks”, Networks, 36:3 (2000), 180–190 | 3.0.CO;2-R class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[31] Beivide R., Herrada E., Balcazar J. L., Arruabarrena A., “Optimal distance networks of low degree for parallel computers”, IEEE Trans. Computers, 40:10 (1991), 1109–1124 | DOI | MR

[32] Beivide R., Martinez C., Izu C., et al., “Chordal Topologies for Interconnection Networks”, LNCS, 2858, 2003, 385–392

[33] Bermond J.-C., Comellas F., Hsu D. F., “Distributed loop computer networks: a survey”, J. Parallel Distributed Comput., 24 (1995), 2–10 | DOI

[34] Bermond J.-C., Favaron O., Maheo M., “Hamiltonian decomposition of Cayley graphs of degree four”, J. Combin. Theory. Ser. B, 46 (1989), 142–153 | DOI | MR | Zbl

[35] Bermond J.-C., Illiades G., Peyrat C., “An optimization problem in distributed loop computer networks”, Third Inter. Conf. Combinatorial Math. (New York, USA, June 1985), Ann. New York Acad. Sci., 555, 1989, 45–55 | MR | Zbl

[36] Bermond J.-C., Tzvieli D., “Minimal diameter double-loop networks: Dense optimal families”, Networks, 21 (1991), 1–9 | DOI | MR | Zbl

[37] Boesch F. T., Tindell R., “Circulants and their connectivity”, J. Graph Theory, 8 (1984), 487–499 | DOI | MR | Zbl

[38] Boesch F. T., Wang J.-F., “Reliable circulant networks with minimum transmission delay”, IEEE Trans. Circuits Syst., 32 (1985), 1286–1291 | DOI | MR | Zbl

[39] Browne R. F., Hodgson R. M., “Symmetric degree-four chordal ring networks”, IEEE Proc., 137:4 (1990), 310–318

[40] Cai J.-Y., Havas G., Mans B., et al., “On Routing in Circulant Graphs”, LNCS, 1627, 1999, 360–369 | MR

[41] Chen S., Jia X.-D., “Undirected loop networks”, Networks, 23 (1993), 257–260 | DOI | MR | Zbl

[42] Chen B.-X., Meng J.-X., Xiao W.-J., “A Constant Time Optimal Routing Algorithm for Undirected Double-Loop Networks”, First Int. Conf. Mobile Ad-hoc and Sensor Networks, MSN 2005 (Wuhan, China, December 2005), 309–316

[43] Chen B.-X., Meng J.-X., Xiao W.-J., “Some new optimal and suboptimal infinite families of undirected double-loop networks”, DMTCS, 8 (2006), 299–312 | MR

[44] Chen B.-X., Xiao W.-J., Parhami B., “Diameter formulas for a class of undirected double-loop networks”, J. Intercon. Networks, 6:1 (2005), 1–15 | DOI | Zbl

[45] Comellas F., Mitjana M., Peters J. G., “Broadcasting in Small-World Communication Networks”, 9th Inter. Coll. on Structural Information and Communication Complexity, SIROCCO 9, Proc. Informatics, 13, 2002, 73–85

[46] David H. A., “Enumeration of cyclic graphs and cyclic designs”, J. Comb. Theory, 13 (1972), 303–308 | DOI | MR | Zbl

[47] Davis P. J., Circulant Matrices, Wiley Publ., New York, 1979, 304 pp. | MR

[48] Delorme C., Maheo M., “Isomorphisms of cayley multigraphs of degree four on finite abelian groups”, Eur. J. Combinat., 13 (1992), 59–61 | DOI | MR | Zbl

[49] Du D.-Z., Hsu D. F., Li Q., Xu J., “A combinatorial problem related to distributed loop networks”, Networks, 20 (1990), 173–180 | DOI | MR | Zbl

[50] Elspas B., “Topological constructions on interconnection limited logic”, Switch. Circ. Theor. Log. Des., 164 (1964), 133–147

[51] Elspas B., Turner J., “Graphs with circulant adjacency matrices”, J. Comb. Theory, 9 (1970), 229–240 | MR

[52] Fabrega J., Zaragoza M., “Fault-tolerant routings in double fixed-step networks”, Discr. Appl. Math., 78 (1997), 61–74 | DOI | MR | Zbl

[53] Feng X., Xu M., “On isomorphisms of Cayley graphs of small valency”, Algebra Colloquium, 1 (1994), 67–76 | MR

[54] Garcia C., Solé P., “Diameter lower bound for Waring graphs and multiloop networks”, Discr. Math., 111 (1993), 257–261 | DOI | MR | Zbl

[55] Gavoille C., “A survey on interval routing”, Theor. Comp. Sci., 245 (2000), 217–253 | DOI | MR | Zbl

[56] Gobel F., Neutel E. A., “Cyclic graphs”, Discr. Appl. Math., 99 (2000), 3–12 | DOI | MR

[57] Gomez D., Gutierrez J., Ibeas A., Beivide R., “Optimal routing in double loop networks”, Theor. Comp. Sci., 381:1–3 (2007), 68–85 | DOI | MR | Zbl

[58] Harutyunyan H. A., Maraachlian E., “Near Optimal Broadcasting in Optimal Triple Loop Graphs”, IEEE 22nd Inter. Conf. on Advanced Information Networking and Applications, AINA 2008 (March 25–29, 2008, Ginowan, Okinawa, Japan), 167–181

[59] Hedetniemi S. M., Hedetniemi S. T., Liestman A. L., “A survey of gossiping and broadcasting in communication networks”, Networks, 18 (1988), 319–349 | DOI | MR | Zbl

[60] Hsu D. F., Jia X. D., “Extremal problems in the combinatorial construction of distributed loop networks”, SIAM J. Discr. Math., 7 (1994), 57–71 | DOI | MR | Zbl

[61] Hsu D. F., Shapiro J., “Bounds for the minimal number of transmission delays in double loop networks”, J. Combinat. Inform. Syst. Sci., 16 (1991), 55–62 | MR | Zbl

[62] Hsu D. F., Shapiro J., “A census of tight one-optimal double loop networks”, Graph Theory, Combinatorics, Algorithms and Applications, eds. J. Alavi et al., SIAM, 1991, 254–265 | MR

[63] Huber K., “Codes over Tori”, IEEE Trans. Inform. Theor., 43:2 (1997), 740–744 | DOI | MR | Zbl

[64] Hwang F. K., “A complementary survey on double-loop networks”, Theor. Comp. Sci., 263 (2001), 211–229 | DOI | MR | Zbl

[65] Hwang F. K., “A survey on multi-loop networks”, Theor. Comp. Sci., 299 (2003), 107–121 | DOI | MR | Zbl

[66] Imase M., Iton M., “Desing to minimize diameter building-block networks”, IEEE Trans. Comput., C30 (1981), 439–442 | DOI | MR | Zbl

[67] Jia X.-D., Su W., “Triple Loop Networks with Minimal Transmission Delay”, Int. J. Found. Comp. Sci., 8:3 (1997), 305–328 | DOI | Zbl

[68] Kotsis G., “Interconnection Topologies and Routing for Parallel Processing Systems”, Austrian–Hungarian Workhop, Technical Report, KFKI, 1992, 95–106

[69] LaForge L. E., Korver K. F., Fadali M. S., “What Designers of Bus and Network Architectures Should Know about Hypercubes”, IEEE Trans. Comput., 52:4 (2003), 525–544 | DOI | MR

[70] Li C. H., “On isomorphisms of finite Cayley graphs – a survey”, Discr. Math., 256:1–2 (2002), 301–334 | MR | Zbl

[71] Liaw S.-C., Chang G. J., Cao F., Hsu D. F., “Fault-tolerant Routing in Circulant Networks and Cycle Prefix Networks”, Ann. Comb., 2 (1998), 165–172 | DOI | MR | Zbl

[72] Liestman A. L., Opatrny J., Zaragoza M., “Network Properties of Double and Triple Fixed-Step Graphs”, Int. J. Found. Comp. Sci., 9 (1998), 57–76 | DOI | Zbl

[73] Mans B., “On the Interval Routing of Chordal Rings”, Inter. Symposium on Parallel Architectures, Algorithms and Networks, ISPAN 1999, IEEE Computer Society, Australia, 1999, 16–21

[74] Mans B., Pappalardi F., Shparlinski I., “On the Adam Conjecture on Circulant Graphs”, LNCS, 1449, 1998, 251–260 | MR | Zbl

[75] Mans B., Pappalardi F., Shparlinski I., “On the spectral Adam property for circulant graphs”, Discr. Math., 254:1–3 (2002), 309–329 | DOI | MR | Zbl

[76] Mans B., Shparlinski I., “Bisecting and Gossiping in Circulant Graphs”, LNCS, 2976, 2004, 589–598 | MR | Zbl

[77] Martinez C., Beivide R., Izu C., Miguel-Alonso J., “Characterization of the Class of Optimal Dence Circulant Graphs of Degree Four”, XIV Jornadas de Paralelismo, Leganes, Septiembre 2003, 1–6

[78] Martinez C., Beivide R., Stafford E., et al., “Modeling Toroidal Networks with the Gaussian Integers”, IEEE Trans. Comput., 57:8 (2008), 1046–1056 | DOI | MR

[79] Monakhova E. A., “Optimal circulant computer networks”, Inter. Conf. “Parallel Computing Technologies” (Novosibirsk, USSR), World Scientific, Singapore, 1991, 450–458

[80] Monakhova E. A., “Algorithms and lower bounds for p-gossiping in circulant networks”, Third Inter. Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN' 97 (Taipei, Taiwan, Dec. 1997), IEEE Computer Society, Los Alamitos, California, 132–137

[81] Monakhova E. A., “Optimal Triple Loop Networks with Given Transmission Delay: Topological Design and Routing”, Inter. Network Optimization Conference, INOC' 2003, Evry–Paris, France, 2003, 410–415

[82] Monakhov O. G., Monakhova E. A., “Computer Discovery of Analytical Descriptions of Families of Circulant Networks”, 6th Inter. Conf. on Soft Computing and Measurements, SCM' 2003 (July 25–27, 2003, St.-Petersburg, Russia), v. 1, 2003, 345–348

[83] Monakhov O. G., Monakhova E. A., “An Algorithm for Discovery of New Families of Optimal Regular Networks”, Lect. Notes Artific. Intell., 2843, 2003, 244–254

[84] Muga F. P., “Undirected circulant graphs”, Inter. Symp. on Parallel Architectures, Algorithms and Networks, IEEE, 1994, 113–118

[85] Muga F. P., “Maximal Order of 3- and 5-Regular Circulant Graphs”, Matimyas Matematika, 22:3 (1999), 33–38 | MR | Zbl

[86] Muga F. P., Yu W. E., “A Proposed Topology for a 192-Processor Symmetric Cluster with a Single-Switch Delay”, Proceedings of the First Philippine Computing Science Congress, Manila, Philippines, Nov. 2000, 10 pp.

[87] Mukhopadhyaya K., Sinha B. P., “Fault-tolerant routing in distributed loop networks”, IEEE Trans. Comput., 44:12 (1995), 1452–1456 | DOI | Zbl

[88] Muzychuk M., “On Adam's conjecture for circulant graphs”, Discr. Math., 167–168 (1997), 497–510 | DOI | MR | Zbl

[89] Muzychuk M. E., Tinhofer G., “Recognizing circulant graphs of prime order in polynomial time”, The Electr. J. Combinat., 5:1 (1998), R25, 501–528 | MR

[90] Narayanan L., Opatrny J., “Compact routing on chordal rings of degree four”, Sirocco 97, Proc. of the 4th Inter. Colloquium on Structural Information and Communication Complexity, eds. D. Krizanc, P. Widmayer, Carleton Scientific, Ascona, Switzerland, 1997, 125–137

[91] Narayanan L., Opatrny J., Sotteau D., “All-to-All Optical Routing in Chordal Rings of Degree Four”, Algorithmica, 31:2 (2001), 155–178 | MR | Zbl

[92] Obradovic N., Peters J., Ruzic G., “Reliable Broadcasting in Double Loop Networks”, Networks, 46:2 (2005), 88–97 | DOI | MR | Zbl

[93] Parhami B., “A Class of Odd-Radix Chordal Ring Networks”, J. Comput. Sci. Engin., 4:2–4 (2006), 1–9

[94] Parhami B., “Chordal Rings Based on Symmetric Odd-Radix Number Systems”, Inter. Conf. on Communications in Computing (Las Vegas, NV, June 27–30, 2006), 196–199

[95] Park J.-H., Chwa K.-Y., “Recursive Circulant: a New Topology for Multicomputer Networks”, Proc. of the Inter. Symp. on Parallel Architectures, Algorithms, and Networks, I-SPAN' 94, IEEE Computer Society Press, Kanazawa, Japan, 1994, 73–80

[96] Pelc A., “Fault-Tolerant Broadcasting and Gossiping in Communication Networks”, Networks, 28 (1996), 143–156 | 3.0.CO;2-N class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[97] Puente V., Gregorio J.-A., Prellezo J. M., et al., “Adaptive Bubble Router: a Design to Balance Latency and Thoughput in Networks for Parallel Computers”, Proc. of the 1999 Inter. Conf. on Parallel Processing, ICPP' 99, IEEE Computer Society, September, 1999, 58–67

[98] Puente V., Izu C., Gregorio J.-A., et al., “Improving Parallel System Performance by Changing the Arrangement of the Network Links”, Intern. Conf. on Supercomputing (May 2000), ACM, Santa Fe, New Mexico, USA, 2000, 44–53

[99] Robic̆ B., Optimal routing in 2-jump circulant networks, Tech. Report No 397, University of Cambridge Computer Laboratory, Cambridge, 1996, 7 pp.

[100] Robic̆ B., Z̃erovnik J., “Minimum 2-terminal routing in 2-jump circulant graphs”, Comput. Artific. Intell., 19:1 (2000), 37 | MR | Zbl

[101] Sampels M., “Cayley graphs as interconnection networks: A case study”, Inter. Conf. Parcella' 96, Akademie Verlag, Berlin, 1996, 67–76

[102] Sampels M., “Large networks with small diameter”, Inter. Workshop on Graph Theoretic Concepts in Computer Science, WG' 97, Springer, Berlin, 1997, 288–302 | Zbl

[103] Schinder M., “New architectures keep pace with throughput needs”, Electr. Design., 5 (1981), 97–106

[104] Shin K. G., “HARTS: A Distributed Real-Time Architecture”, Computer, 24:5 (1991), 25–35 | DOI

[105] Stojmenovic I., “Multiplicative circulant networks. Topological properties and communication algorithms”, Discr. Appl. Math., 77 (1997), 281–305 | DOI | MR | Zbl

[106] Stone H. S., “The organization of high-speed memory for parallel block transfer data”, IEEE Trans. Comput., 19 (1970), 47–53 | DOI | Zbl

[107] Toueg S., Steiglitz K., “The desing of small diameter networks by local search”, IEEE Trans. Comput., 28 (1979), 537–542 | DOI | MR | Zbl

[108] Turner J., “Point-symmetric graphs with a prime number of points”, J. Combin. Theory, 3 (1967), 136–145 | DOI | MR | Zbl

[109] Tzvieli D., “Minimal diameter double-loop networks. I. Large infinite optimal families”, Networks, 21 (1991), 387–415 | DOI | MR | Zbl

[110] Wilkov R. S., “Analysis and design of reliable computer networks”, IEEE Trans. Comput., 20:3 (1972), 660–678 | DOI

[111] Wong C. K., Coppersmith D., “A combinatorial problem related to multimodule memory organizations”, J. Assoc. Comput. Mach., 21 (1974), 392–402 | MR | Zbl

[112] Wong C. K., Maddocks T. W., “A generalized Pascal's triangle”, Fibonacci Quart., 13 (1975), 134–136 | MR | Zbl

[113] Yang Y., Funashashi A., Jouraku A., et al., “Recursive Diagonal Torus: An Interconnection Network for Massively Parallel Computers”, IEEE Trans. Parallel and Distributed Systems, 12:7 (2001), 701–715 | DOI

[114] Yebra J. L. A., Fiol M. A., Morillo P., Alegre I., “The diameter of undirected graphs associated to plane tessellations”, Ars Combinat., 20:B (1985), 159–172 | MR | Zbl

[115] Z̃erovnik J., Pisanski T., “Computing the diameter in multiple-loop networks”, J. Algorithms, 14 (1993), 226–243 | DOI | MR | Zbl