×

Forwarding and optical indices of 4-regular circulant networks. (English) Zbl 1343.05141

Summary: An all-to-all routing in a graph \(G\) is a set of oriented paths of \(G\), with exactly one path for each ordered pair of vertices. The load of an edge under an all-to-all routing \(R\) is the number of times it is used (in either direction) by paths of \(R\), and the maximum load of an edge is denoted by \(\pi(G,R)\). The edge-forwarding index \(\pi(G)\) is the minimum of \(\pi(G,R)\) over all possible all-to-all routings \(R\), and the arc-forwarding index \(\overrightarrow{\pi}(G)\) is defined similarly by taking direction into consideration, where an arc is an ordered pair of adjacent vertices. Denote by \(w(G,R)\) the minimum number of colours required to colour the paths of \(R\) such that any two paths having an edge in common receive distinct colours. The optical index \(w(G)\) is defined to be the minimum of \(w(G,R)\) over all possible \(R\), and the directed optical index \(\overrightarrow{w}(G)\) is defined similarly by requiring that any two paths having an arc in common receive distinct colours. In this paper we obtain lower and upper bounds on these four invariants for 4-regular circulant graphs with connection set \(\{ \pm 1, \pm s \}\), \(1 < s < n/2\). We give approximation algorithms with performance ratio a small constant for the corresponding forwarding index and routing and wavelength assignment problems for some families of 4-regular circulant graphs.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Amar, D.; Raspaud, A.; Togni, O., All-to-all wavelength-routing in all-optical compound networks, Discrete Math., 235, 1-3, 353-363 (2001) · Zbl 0977.05132
[2] Beauquier, B., All-to-all communication for some wavelength-routed all-optical networks, Networks, 33, 3, 179-187 (1999) · Zbl 0940.90018
[3] Beauquier, B.; Bermond, J. C.; Gargano, L.; Hell, P.; Perennes, S.; Vaccaro, U., Graph problems arising from wavelength-routing in all-optical networks, (2nd Workshop on Optics and Computer Science (WOCS) (1997))
[4] Beauquier, B.; Pérennes, S.; Tóth, D., All-to-all routing and coloring in weighted trees of rings, (Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures. Proceedings of the 11th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA’99 (1999), ACM), 185-190
[5] Bermond, J. C.; Comellas, F.; Hsu, D. F., Distributed loop computer networks: a survey, J. Parallel Distrib. Comput., 24, 1, 2-10 (1995)
[6] Bermond, J. C.; Gargano, L.; Perennes, S.; Rescigno, A. A.; Vaccaro, U., Efficient collective communication in optical networks, Theor. Comput. Sci., 233, 1-2, 165-189 (2000) · Zbl 0961.90020
[7] Bian, Z.; Gu, Q.; Zhou, X., Efficient algorithms for wavelength assignment on trees of rings, Discrete Appl. Math., 157, 5, 875-889 (2009) · Zbl 1187.68019
[8] Chen, B.; Xiao, W.; Parhami, B., Diameter formulas for a class of undirected double-loop networks, J. Interconnect. Net., 6, 1, 1-15 (2005)
[9] Deng, X.; Li, G.; Zang, W.; Zhou, Y., A 2-approximation algorithm for path coloring on a restricted class of trees of rings, J. Algorithms, 47, 1, 1-13 (2003) · Zbl 1045.68152
[10] Fang, X. G.; Li, C. H.; Praeger, C. E., On orbital regular graphs and Frobenius graphs, Discrete Math., 182, 1-3, 85-99 (1998) · Zbl 0904.05038
[11] Fertin, G.; Raspaud, A., A survey on Knödel graphs, Discrete Appl. Math., 137, 2, 173-195 (2004) · Zbl 1062.68086
[12] Gargano, L.; Vaccaro, U., Routing in All-Optical Networks: Algorithmic and Graph-Theoretic Problems, Numbers, Information and Complexity, 555-578 (2000), Springer · Zbl 0980.05046
[13] Gargano, L.; Hell, P.; Perennes, S., Colouring paths in directed symmetric trees with applications to WDM routing, (Automata, Languages and Programming. Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 1256 (1997)), 505-515 · Zbl 1401.68245
[14] Gauyacq, G.; Micheneau, C.; Raspaud, A., Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition, (Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science, vol. 1517 (1998), Springer), 227-241 · Zbl 0936.68074
[15] Gómez, D.; Gutierrez, J.; Ibeas, Á., Optimal routing in double loop networks, Theor. Comput. Sci., 381, 1-3, 68-85 (2007) · Zbl 1188.68213
[16] Heydemann, M. C., Cayley graphs and interconnection networks, (Hahn, G.; Sabidussi, G., Graph Symmetry (1997), Kluwer Academic Publishing: Kluwer Academic Publishing Dordrecht), 167-224 · Zbl 0885.05075
[17] Heydemann, M. C.; Meyer, J. C.; Sotteau, D., On forwarding indices of networks, Discrete Appl. Math., 23, 2, 103-123 (1989) · Zbl 0681.90077
[18] Hwang, F. K., A complementary survey on double-loop networks, Theor. Comput. Sci., 263, 1-2, 211-229 (2001) · Zbl 0974.68003
[19] Hwang, F. K., A survey on multi-loop networks, Theor. Comput. Sci., 299, 1-3, 107-121 (2003) · Zbl 1038.68004
[20] Kosowski, A., Forwarding and optical indices of a graph, Discrete Appl. Math., 157, 2, 321-329 (2009) · Zbl 1200.05239
[21] Mans, B.; Shparlinski, I., Bisecting and gossiping in circulant graphs, (LATIN 2004: Theoretical Informatics. LATIN 2004: Theoretical Informatics, Lecture Notes in Computer Science, vol. 2976 (2004), Springer), 589-598 · Zbl 1196.68175
[22] Schröder, H.; Sýkora, O.; Vrt’o, I., Optical all-to-all communication for some product graphs (extended abstract), (SOFSEM’97: Theory and Practice of Informatics. SOFSEM’97: Theory and Practice of Informatics, Lecture Notes in Computer Science, vol. 1338 (1997), Springer), 555-562
[23] Solé, P., The edge-forwarding index of orbital regular graphs, Discrete Math., 130, 1-3, 171-176 (1994) · Zbl 0807.05037
[24] Stojmenović, I., Multiplicative circulant networks topological properties and communication algorithms, Discrete Appl. Math., 77, 3, 281-305 (1997) · Zbl 0879.68080
[25] Thomson, A.; Zhou, S., Frobenius circulant graphs of valency four, J. Aust. Math. Soc., 85, 269-282 (2008) · Zbl 1167.05036
[26] Thomson, A.; Zhou, S., Gossiping and routing in undirected triple-loop networks, Networks, 55, 4, 341-349 (2010) · Zbl 1202.90045
[27] Thomson, A.; Zhou, S., Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes, Eur. J. Comb., 38, 61-78 (2014) · Zbl 1282.05066
[28] Xu, J. M.; Xu, M., The forwarding indices of graphs - a survey, Opusc. Math., 33, 2, 345-372 (2013) · Zbl 1290.05093
[29] Xu, M.; Xu, J.-M.; Sun, L., The forwarding index of the circulant networks, J. Math., 27, 6, 623-629 (2007) · Zbl 1150.05367
[30] Yuan, J.; Zhang, J. Y.; Zhou, S., Routing permutations and involutions on optical ring networks: complexity results and solution to an open problem, J. Discrete Algorithms, 5, 3, 609-621 (2007) · Zbl 1130.68023
[31] Žerovnik, J.; Pisanski, T., Computing the diameter in multiple-loop networks, J. Algorithms, 14, 2, 226-243 (1993) · Zbl 0764.68137
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.