No Access

A SURVEY ON UNDIRECTED CIRCULANT GRAPHS

E. A. MONAKHOVA

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Pr. Lavrentieva, 6, Novosibirsk, 630090, Russia

Search for more papers by this author

https://doi.org/10.1142/S1793830912500024Cited by:43 (Source: Crossref)

Abstract

Circulant graphs have been extensively investigated over the past 30 years because of their broad application to different fields of theory and practice. Two known surveys on circulant networks including a survey on undirected circulants have been published: by Bermond et al. [Distributed loop computer networks: A survey, J. Parallel Distributed Comput.24 (1995) 2–10] and by Hwang [A survey on multi-loop networks, Theoret. Comput. Sci.299 (2003) 107–121]. The present paper includes the results which have not been presented there, in particular the works of Russian researchers, and also a lot of new results obtained in the area of research of circulant networks. We focus on the survey connected with study of structural and communicative properties of circulant networks.

Keywords:

AMSC: 05C35

References

A. Ádám, J. Combin. Theory 2, 393 (1967). Google Scholar
F. Aguilo, M. A. Fiol and C. Garcia, Discrete Math. 168, 3 (1997). Google Scholar
G. A. Anderson and E. D. Jensen, Comput. Surv. 7(4), 197 (1985), DOI: 10.1145/356654.356658. Crossref, Google Scholar
B. W. Arden and H. Lee, IEEE Trans. Comput. C 30, 291 (1981). Google Scholar
G. T. Artamonov, Topology of Regular Computer Networks and Environments (Radio i Svyaź, Moscow, 1985) (in Russian) . Google Scholar
A. T. Balaban, Graph Theoretical Approaches to Chemical Reactivity, eds. D. Bonchev and O. Mekenyan (Kluwer Academic Publishers, The Netherlands, 1994) pp. 137–180. Crossref, Google Scholar
G. H. Barneset al., IEEE Trans. Comput. 17, 746 (1968). Google Scholar
L. Barriereet al., Networks 36(3), 180 (2000). Crossref, Google Scholar
R. Beivideet al., IEEE Trans. Comput. 40(10), 1109 (1991), DOI: 10.1109/12.93744. Crossref, Google Scholar
R. Beivideet al., Lect. Notes Comput. Sci. 2858, 385 (2003), DOI: 10.1007/978-3-540-39707-6_33. Crossref, Google Scholar
J.-C. Bermond, F. Comellas and D. F. Hsu, J. Parallel Distributed Comput. 24, 2 (1995), DOI: 10.1006/jpdc.1995.1002. Crossref, Google Scholar
J.-C. Bermond, C. Delorme and G. Farhi, J. Combin. Theory Ser. B 36, 32 (1984), DOI: 10.1016/0095-8956(84)90012-1. Crossref, Google Scholar
J.-C. Bermond, O. Favaron and M. Maheo, J. Combin. Theory Ser. B 46, 142 (1989), DOI: 10.1016/0095-8956(89)90040-3. Crossref, Google Scholar
J.-C. Bermond, G. Illiades and C. Peyrat, Ann. New York Acad. Sci. 555, 45 (1989). Crossref, Google Scholar
J.-C. Bermond and D. Tzvieli, Networks 21, 1 (1991), DOI: 10.1002/net.3230210102. Crossref, Google Scholar
F. T. Boesch and R. Tindell, J. Graph Theory 8, 487 (1984), DOI: 10.1002/jgt.3190080406. Crossref, Google Scholar
F. T. Boesch and J.-F. Wang, IEEE Trans. Circuits Syst. 32, 1286 (1985), DOI: 10.1109/TCS.1985.1085667. Crossref, Google Scholar
R. F. Browne and R. M. Hodgson, IEE Proc. 137(4), 310 (1990). Google Scholar
J.-Y. Caiet al., On routing in circulant graphs, Int. Conf. COCOON'991627, Lect. Notes Comput. Sci (Springer-Verlag, Berlin, 1999) pp. 360–369. Google Scholar
N. Chalamaiah and B. Ramamurty, Inform. Process. Lett. 67, 157 (1998), DOI: 10.1016/S0020-0190(98)00099-4. Crossref, Google Scholar
S. Chen and X.-D. Jia, Networks 23, 257 (1993), DOI: 10.1002/net.3230230407. Crossref, Google Scholar
B.-X. Chen, J.-X. Meng and W.-J. Xiao, A constant time optimal routing algorithm for undirected double-loop networks, First Int. Conf. Mobile Ad-hoc and Sensor Networks (MSN 2005) (Springer Verlag, Berlin, 2005) pp. 308–316. Google Scholar
B.-X. Chen, J.-X. Meng and W.-J. Xiao, Discrete Math. Theoret. Comput. Sci. 8, 299 (2006). Crossref, Google Scholar
B.-X. Chen, W.-J. Xiao and B. Parhami, J. Interconnection Netw. 6(1), 2005 (2005). Google Scholar
F. Comellas, M. Mitjana and J. G. Peters, Broadcasting in small-world communication networks, 9th Int. Coll. Structural Information and Communication Complexity (SIROCCO 9)13, Proceedings in Informatics (2002) pp. 73–85. Google Scholar
Cray T3D System architecture overview, Technical Report, Cray Research, Inc., Minnesota (1994) . Google Scholar
H. A. David, J. Combin. Theory 13, 303 (1972). Crossref, Google Scholar
P. J. Davis , Circulant Matrices ( Wiley , New York , 1979 ) . Google Scholar
C. Delorme and M. Maheo, European J. Combin. 13, 59 (1992), DOI: 10.1016/0195-6698(92)90067-A. Crossref, Google Scholar
Y. Dinitz, M. Feighelstein and S. Zaks, On optimal graphs embedded into paths and rings, with analysis using l1-spheres, 23th Int. Workshop on Graph-Theoretic Concepts in Computer Science (WG 97)1335, Lect. Notes Comput. Sci (Springer, 1997) pp. 171–183. Google Scholar
R. Dougherty and V. Faber, SIAM J. Discrete Math. 17(3), 478 (2004), DOI: 10.1137/S0895480100372899. Crossref, Google Scholar
D.-Z. Duet al., Networks 20, 173 (1990), DOI: 10.1002/net.3230200204. Crossref, Google Scholar
B. Elspas, Switching Circuit Theory Logic Design 164, 133 (1964). Google Scholar
B. Elspas and J. Turner, J. Combin. Theory 9, 229 (1970). Google Scholar
S. A. Evdokimov and I. N. Ponomarenko, St. Petersburg Math. J. 15, 813 (2004), DOI: 10.1090/S1061-0022-04-00833-7. Crossref, Google Scholar
J. Fabrega and M. Zaragoza, Discrete Appl. Math. 78, 61 (1997), DOI: 10.1016/S0166-218X(97)00015-2. Crossref, Google Scholar
C. Garcia and P. Solé, Discrete Math. 111, 257 (1993), DOI: 10.1016/0012-365X(93)90160-U. Crossref, Google Scholar
C. Gavoille, Theoret. Comput. Sci. 245, 217 (2000), DOI: 10.1016/S0304-3975(99)00283-2. Crossref, Google Scholar
F. Gobel and E. A. Neutel, Discrete Appl. Math. 99, 3 (2000). Crossref, Google Scholar
D. Gomezet al., Theoret. Comput. Sci. 381(3), 68 (2007). Crossref, Google Scholar
H. A. Harutyunyan and E. Maraachlian, Near optimal broadcasting in optimal triple loop graphs, IEEE 22nd Int. Conf. Advanced Information Networking and Applications, AINA 2008 pp. 167–181. Google Scholar
S. M. Hedetniemi, S. T. Hedetniemi and A. L. Liestman, Networks 18, 319 (1988), DOI: 10.1002/net.3230180406. Crossref, Google Scholar
D. F. Hsu and X. D. Jia, SIAM J. Discrete Math. 7, 57 (1994), DOI: 10.1137/S0895480190184811. Crossref, Google Scholar
D. F. Hsu and J. Shapiro, J. Combin. Inform. Syst. Sci. 16, 55 (1991). Google Scholar
D. F. Hsu and J. Shapiro, Graph Theory, Combinatorics, Algorithms and Applications, eds. J. Alaviet al. (SIAM, 1991) pp. 254–265. Google Scholar
K. Huber, IEEE Trans. Inform. Theory 43(2), 740 (1997), DOI: 10.1109/18.556133. Crossref, Google Scholar
F. K. Hwang, Theoret. Comput. Sci. 263, 211 (2001), DOI: 10.1016/S0304-3975(00)00243-7. Crossref, Google Scholar
F. K. Hwang, Theoret. Comput. Sci. 299, 107 (2003), DOI: 10.1016/S0304-3975(01)00341-3. Crossref, Google Scholar
M. Imase and M. Iton, IEEE Trans. Comput. C 30, 439 (1981). Google Scholar
X.-D. Jia and W. Su, Int. J. Found. Comp. Sci. 8(3), 305 (1997), DOI: 10.1142/S0129054197000203. Link, Google Scholar
V. V. Korneev, Comput. Syst. Novosibirsk 60, 17 (1974). Google Scholar
G. Kotsis, Interconnection topologies and routing for parallel processing systems, Austrian–Hungarian workshop, Technical Report, KFKI (1992), pp. 95–106 . Google Scholar
D.-M. Kwai and B. Parhami, Parallel Process. Lett. 6(4), 469 (1996). Link, Google Scholar
D.-M. Kwai and B. Parhami, Computer J. 41(1), 52 (1998), DOI: 10.1093/comjnl/41.1.52. Crossref, Google Scholar
L. E. LaForge, K. F. Korver and M. S. Fadali, IEEE Trans. Comput. 52(4), 525 (2003), DOI: 10.1109/TC.2003.1190592. Crossref, Google Scholar
C. H. Li, Discrete Math. 256(2), 301 (2002), DOI: 10.1016/S0012-365X(01)00438-1. Crossref, Google Scholar
S.-C. Liawet al., Ann. Combin. 2, 165 (1998), DOI: 10.1007/BF01608486. Crossref, Google Scholar
A. L. Liestman, J. Opatrny and M. Zaragoza, Int. J. Found. Comp. Sci. 9, 57 (1998), DOI: 10.1142/S0129054198000076. Link, Google Scholar
B. Mans, On the interval routing of chordal rings, Int. Symp. Parallel Architectures, Algorithms and Networks (ISPAN 1999) (IEEE Computer Society, 1999) pp. 16–21. Google Scholar
B. Mans, F. Pappalardi and I. Shparlinski, On the Adam conjecture on circulant graphs, Fourth Annual Int. Computing and Combinatorics Conference (COCOON'98)1449, Lecture Notes in Computer Science (Springer, Berlin, 1998) pp. 251–260. Google Scholar
B. Mans, F. Pappalardi and I. Shparlinski, Discrete Math. 254(3), 309 (2002), DOI: 10.1016/S0012-365X(01)00374-0. Crossref, Google Scholar
B. Mans and I. Shparlinski, Bisecting and gossiping in circulant graphs, 6th Latin American Theoretical Informatics Conf.2976, Lecture Notes in Computer Science (Springer-Verlag, Berlin, 2004) pp. 589–598. Google Scholar
C. Martinez, R. Beivide, C. Izu and J. Miguel-Alonso, Characterization of the class of optimal dense circulant graphs of degree four, in XIV Jornadas de Paralelismo. Leganes, September 2003, 1–6 . Google Scholar
C. Martinezet al., IEEE Trans. Comput. 57(8), 1046 (2008). Google Scholar
C. Martinezet al., Problems Inform. Transmission 44(1), 1 (2008). Crossref, Google Scholar
O. G. Monakhov, Comput. Syst. Novosibirsk 80, 3 (1979). Google Scholar
O. G. Monakhov, Optoelectronics, Instrumentation and Data Processing 1 (Allerton Press Inc., New York, 2006) pp. 106–116. Google Scholar
E. A. Monakhova, Comput. Syst. Novosibirsk 80, 18 (1979). Google Scholar
E. A. Monakhova, Comput. Syst. Novosibirsk 90, 81 (1981). Google Scholar
E. A. Monakhova, Comput. Syst. Novosibirsk 94, 81 (1982). Google Scholar
E. A. Monakhova, Electron. Model. (Gordon and Breach) 7(3), 564 (1988). Google Scholar
E. A. Monakhova, Optimal circulant computer networks, Int. Conf. "Parallel Computing Technologies", ed. N. N. Mirenkov (World Scientific, Singapore, 1991) pp. 450–458. Google Scholar
E. A. Monakhova, Algorithms and lower bounds for p-gossiping in circulant networks, Third Int. Symp. Parallel Architectures, Algorithms, and Networks (I-SPAN'97) (IEEE Computer Society, Los Alamitos, CA, 1997) pp. 132–137. Google Scholar
E. A. Monakhova, Optimal triple loop networks with given transmission delay: Topological design and routing, Int. Network Optimization Conf., eds. W. Ben-Ameur and A. Petrowski (Institut National des Telecommunications, 2003) pp. 410–415. Google Scholar
E. A. Monakhova, Optoelectronics, Instrumentation and Data Processing 3 (Allerton Press Inc., New York, 2006) pp. 90–101. Google Scholar
E. A. Monakhova, Discrete Anal. Oper. Res. 16(4), 47 (2009). Google Scholar
E. A. Monakhova, Discrete Anal. Oper. Res. 17(5), 56 (2010). Google Scholar
E. A. Monakhova, Discrete Anal. Oper. Res. 18(1), 66 (2011). Google Scholar
O. G. Monakhov and E. A. Monakhova, Computer discovery of analytical descriptions of families of circulant networks, 6th Int. Conf. Soft Computing and Measurements (SCM'2003)1 pp. 345–348. Google Scholar
O. G. Monakhov and E. A. Monakhova, Parallel Systems with Distributed Memory: Structures and Organization of Interactions (SB RAS, Novosibirsk, 2000) (in Russian) . Google Scholar
O. G. Monakhov and E. A. Monakhova, Int. Sci. J. Comput. Syst. 4(2), 85 (2000). Google Scholar
O. G. Monakhov and E. A. Monakhova, An algorithm for discovery of new families of optimal regular networks, 6th Int. Conf. Discovery Science (DS 2003)2843, Lecture Notes in Artificial Intelligence (Springer-Verlag, Berlin, 2003) pp. 244–254. Google Scholar
P. Morillo, F. Comelas and M. A. Fiol, Communication Technology (World Scientific, 1987) pp. 295–299. Google Scholar
F. P. Muga, Undirected circulant graphs, Int. Symp. Parallel Architectures, Algorithms and Networks (IEEE, 1994) pp. 113–118. Google Scholar
F. P. Muga II, Matimyas Matematika 22(3), 1 (1999). Google Scholar
F. P. Muga and W. E. S. Yu, A proposed topology for a 192-processor symmetric cluster with a single-switch delay, First Philippine Computing Science Congress (2000) p. 10. Google Scholar
K. Mukhopadhyaya and B. P. Sinha, IEEE Trans. Comput. 44(12), 1452 (1995), DOI: 10.1109/12.477250. Crossref, Google Scholar
M. Muzychuk, Discrete Math. 168, 497 (1997). Google Scholar
M. E. Muzychuk and G. Tinhofer, Electron. J. Combin. 5(1), 501 (1998). Google Scholar
L. Narayanan and J. Opatrny, Compact routing on chordal rings of degree four, Sirocco 97, eds. D. Krizanc and P. Widmayer (Carleton Scientific, 1997) pp. 125–137. Google Scholar
L. Narayanan, J. Opatrny and D. Sotteau, Algorithmica 31(2), 155 (2001), DOI: 10.1007/s00453-001-0043-5. Crossref, Google Scholar
R. Nedela and M. Skoviera, J. Graph Theory 19(1), 1 (2006), DOI: 10.1002/jgt.3190190102. Crossref, Google Scholar
B. B. Nesterenko and M. A. Novotarskiy, Artificial Intell. 3, 132 (2009). Google Scholar
N. Obradovic, J. Peters and G. Ruzic, Networks 46(2), 88 (2005). Crossref, Google Scholar
B. Parhami, CS'J J. Comput. Sci. Eng. 4(4), 1 (2006). Google Scholar
B. Parhami, Chordal rings based on symmetric odd-radix number systems, Int. Conf. Communications in Computing (2006) pp. 196–199. Google Scholar
B. Parhami and D.-M. Kwai, IEEE Trans. Parallel Distrib. Syst. 10(6), 658 (1999), DOI: 10.1109/71.774913. Crossref, Google Scholar
J.-H. Park and K.-Y. Chwa, Recursive Circulant: A New Topology for Multicomputer Networks (IEEE, 1994) pp. 73–80. Google Scholar
J. M. Pedersen, T. M. Riaz and O. B. Madsen, Distances in generalized double rings and degree three chordal rings, IASTED Int. Conf. on Parallel and Distributed Computing and Networks (IASTED PDCN2005) (2005) pp. 153–158. Google Scholar
J. M. Pedersen, T. M. Riaz and O. B. Madsen, Five novel selection policies for N2R network structures, 8th Int. Conf. on Advanced Communication Technology, IEEE/ICACT20063 (2006) pp. 2174–2179. Google Scholar
A. Pelc, Networks 28, 143 (1996). Crossref, Google Scholar
F. P. Preparata and J. Vuillemin, Commun. ACM 24, 300 (1981), DOI: 10.1145/358645.358660. Crossref, Google Scholar
V. Puenteet al., Adaptive bubble router: A design to balance latency and thoughput in networks for parallel computers, Int. Conf. Parallel Computing (1999) pp. 58–67. Google Scholar
V. Puenteet al., Improving parallel system performance by changing the arrangement of the network links, Int. Conf. Supercomputing (ACM, Sante Fe, New Mexico USA, 2000) pp. 44–53. Google Scholar
V. Puenteet al., Rearranging links to improve the performance of parallel computers: The case of midimew networks, Int. Conf. Supercomputing (ISC'2000) (2000) pp. 44–53. Google Scholar
B. Robic, Optimal routing in 2-jump circulant networks, Technical Report N397, University of Cambridge Computer Laboratory, Cambridge, 1996 . Google Scholar
B. Robic and J. Zerovnik, Comput. Artif. Intell. 19(1), 37 (2000). Google Scholar
M. Sampels, Cayley graphs as interconnection networks: A case study, Int. Conf. Parcella'96 (Akademie-Verlag, Berlin, 1996) pp. 67–76. Google Scholar
M. Sampels, Large networks with small diameter, Int. Workshop Graph on Theoretic Concepts in Computer Science (WG'97) (Springer, Berlin, 1997) pp. 288–302. Google Scholar
M. Schinder, Electron. Des. 5, 97 (1981). Google Scholar
K. G. Shin, Computer 24(5), 25 (1991), DOI: 10.1109/2.76284. Crossref, Google Scholar
I. Stojmenovic, Discrete Appl. Math. 77, 281 (1997). Crossref, Google Scholar
H. S. Stone, IEEE Trans. Comput. 19, 47 (1970). Google Scholar
S. Toueg and K. Steiglitz, IEEE Trans. Comput. 28, 537 (1979). Google Scholar
S. V. Trufanov, Eng. Cybern. 60 (1967). Google Scholar
J. Turner, J. Combin. Theory 3, 136 (1967). Crossref, Google Scholar
D. Tzvieli, Networks 21, 387 (1991), DOI: 10.1002/net.3230210403. Crossref, Google Scholar
V. A. Vorobieb, Comput. Syst. Novosibirsk 60, 35 (1974). Google Scholar
M. E. Watkins, J. Combin. Theory 6, 152 (1969). Crossref, Google Scholar
R. S. Wilkov, IEEE Trans. Comput. 20(3), 660 (1972). Google Scholar
L. D. Wittie, IEEE Trans. Comput. 30(4), 264 (1981). Google Scholar
C. K. Wong and Don Coppersmith, J. Assoc. Comput. Mach. 21, 392 (1974), DOI: 10.1145/321832.321838. Crossref, Google Scholar
C. K. Wong and T. W. Maddocks, Fibonacci Quart. 13, 134 (1975). Google Scholar
Y. Yanget al., IEEE Trans. Parallel Distributed Syst. 12(7), 701 (2001). Crossref, Google Scholar
N. Yanget al., A study of the generalized Petersen graph and a novel graph Y, Workshop on Algorithms and Computational Molecular Biology (ICS2002) (2002) pp. 1–18. Google Scholar
J. L. A. Yebraet al., Ars Combin. B 20B, 159 (1985). Google Scholar
J. Zerovnik and T. Pisanski, J. Algorithms 14, 226 (1993), DOI: 10.1006/jagm.1993.1011. Crossref, Google Scholar