The forwarding indices of graphs - a survey

• Autorzy: Xu J.-M. , Xu M.
• Języki publikacji: EN

Abstrakty

EN

A routing R of a connected graph G of order n is a collection of n(n — 1) simple paths connecting every ordered pair of vertices of G. The vertex-forwarding index £(G,R) of G with respect to a routing R is defined as the maximum number of paths in R passing through any vertex of G. The vertex-forwarding index £(G) of G is defined as the minimum £(G,R) over all routings R of G. Similarly, the edge-forwarding index π (G,R) of G with respect to a routing R is the maximum number of paths in R passing through any edge of G. The edge-forwarding index π (G) of G is the minimum π(G, R) over all routings R of G. The vertex-forwarding index or the edge-forwarding index corresponds to the maximum load of the graph. Therefore, it is important to find routings minimizing these indices and thus has received much research attention for over twenty years. This paper surveys some known results on these forwarding indices, further research problems and several conjectures, also states some difficulty and relations to other topics in graph theory.

Słowa kluczowe

EN

graph theory; vertex-forwarding index; edge-forwarding index; routing; networks

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2013
• Tom: Vol. 33, no. 2
• Strony: 345--372
• Opis fizyczny: Bibliogr. 72 poz.

Twórcy

autor

Xu J.-M.

• University of Science and Technology of China School of Mathematical Sciences Wentsun Wu Key Laboratory of CAS Hefei, Anhui, 230026, China

autor

Xu M.

• Beijing Normal University School of Mathematical Sciences Ministry of Education Laboratory of Mathematics and Complex Systems Beijing, 100875, China

Bibliografia

• [1] D. Amar, A. Raspaud, O. Togni, All-to-all wavelength-routing in all-optical compound networks, Discrete Math. 235 (2001), 353-363.
• [2] E. Arraiz, A. Martinez, O. Meza, M. Ortega, Metaheuristics for computing the forwarding index of a graph, International Transactions in Operation Research 12 (2005), 299-310.
• [3] A. Assad, Multicommodity network flows - a survey, Networks 8 (1978), 37-91.
• [4] B. Beauquier, All-to-all communication in some wavelength-routed all-optical networks Networks 33 (1999), 179-187.
• [5] B. Beauquier, J.C. Bermond, L. Gargano, P. Hell, S. Perennes, U. Vaccaro, Graph problems arising from wavelength routing in all-optical networks, Proc. of the 2nd Workshop on Optics and Computer Science, WOCS'97, Geneva, Switzerland, 1995.
• [6] B. Beauquier, S. Perennes, D. Tóth, All-to-all routing and coloring in weighted trees of rings, Proc. of the 11th ACM Symposium on Parallel Algorithms and Architectures, SPAA'99, 1999, 185-190.
• [7] J.C. Bermond, L. Gargano, S. Perennes, A.A. Rescigno, U. Vaccaro, Efficient collective communication in optical networks, Proc. of the 23rd International Colloquium on Automata, Languages and Programming, ICALP'96, LNCS, vol. 1099, 1996, 574-585.
• [8] S. Bessy, C. Lepelletier, Optical index of fault tolerant routings in WDM networks, Networks 56 (2010) 2, 95-102.
• [9] J. Bialogrodzki, Path Coloring and Routing in Graphs, Graph Colorings, M. Kubale, ed., AMS Contemporary Mathematics, vol. 352, Providence, USA, 2004, 139-152.
• [10] A. Bouabdallah, D. Sotteau, On the edge-forwarding index problem for small graphs, Networks 23 (1993) 4, 249-255.
• [11] M.-C. Cai, Edge-forwarding indices of 2-edge-connected graphs, J. Xinjiang Univ. Natur. Sci. 7 (1990) 4, 11-13.
• [12] G.E. Carlsson, J.E. Cruthirds, H.B. Sexton, C.G. Wright, Interconnection networks based on a generalization of cube-connected cycles, IEEE Transactions on Computers 34 (1985) 8, 769-772.
• [13] C.-P. Chang, T.-Y. Sung, L.-H. Hsu, Edge congestion and topological properties of crossed cubes, IEEE Trans. Parallel and Distributed Systems 11 (2000) 1, 64-80.
• [14] M.-R. Chen, J.-G. Qian, On f-fault tolerant arc-forwarding and optical indices of all-optical folded hypercubes, Information Processing Letters 109 (2009), 828-831.
• [15] S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2002) 2, 71-84.
• [16] F.R.K. Chung, E.G. Jr. Coffman, M.I. Reiman, B. Simon, The forwarding index of communication networks, IEEE Trans. Inform. Theory 33 (1987) 2, 224-232.
• [17] J.H. Dinitz, A.C.H. Ling, D.R. Stinson, Fault tolerant routings with minimum optical index, Networks 48 (2006), 47-54.
• [18] X.-G. Fang, C.-H. Li, C.E. Praeger, On orbital regular graphs and frobenius graphs. Discrete Math. 182 (1998), 85-99.
• [19] W. Fernandez de la Vega, L.M. Gordones, The forwarding indices of random graphs. Random Structures Algorithms 3 (1992) 1, 107-116.
• [20] W. Fernandez de la Vega, Y. Manoussakis, The forwarding index of communication networks with given connectivity, Discrete Appl. Math. 37/38 (1992), 147-155.
• [21] W. Fernandez de le Vega, Y. Manoussakis, Computation of the forwarding index via flows: a note, Networks 24 (1994) 5, 273-276.
• [22] M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979.
• [23] L. Gargano, P. Hell, S. Perennes, Colouring paths in directed symmetric trees with applications to WDM routing, Proc. of the 24th International Colloquium on Automata, Languages and Programming, ICALP'97, LNCS, vol. 1256, 505-515.
• [24] L. Gargano, U. Vaccaro, Routing in all-optical networks: algorithmic and graph-theoretic problems, Numbers, Information and Complexity, Kluwer, Boston, USA, 2000, 555-578.
• [25] G. Gauyacq, On quasi-Cayley graphs, Discrete Appl. Math. 77 (1997), 43-58.
• [26] G. Gauyacq, Edge-forwarding index of star graphs and other Cayley graphs, Discrete Appl. Math. 80 (1997) 2-3, 149-160.
• [27] G. Gauyacq, C. Micheneau, A. Raspaud, Routing in recursive circulant graphs: edge forwarding index and Hamiltonian decomposition, Graph-theoretic concepts in com¬puter science, Smolenice Castle, 1998, 227-241, Lecture Notes in Comput. Sci. 1517, Springer, Berlin, 1998.
• [28] A. Gupta, J. Manuch, L. Stacho, Fault tolerant forwarding and optical indexes: a design theory approach, Lecture Notes Comput Sci. 3104 (2004), 197-208.
• [29] A. Gupta, J. Manuch, L. Stacho, Fault tolerant forwarding and optical indices: A design theory approach, J. Combin. Des. 14 (2006), 25-40.
• [30] M.-C. Heydemann, Cayley graphs and interconnection networks, [in:] Graph Symmetry, G. Hahn and G. Sabidussi, eds., Kluwer Academic Publishers, Netherlands, 1997, 167-224.
• [31] M.-C. Heydemann, J.-C. Meyer, D. Sotteau, On the-forwarding index problem for small graphs, Eleventh British Combinatorial Conference, London, 1987, Ars Combin. 25 (1988), 253-266.
• [32] M.-C. Heydemann, J.-C. Meyer, D. Sotteau, On the-forwarding index of networks, Discrete Appl. Math. 23 (1989) 2, 103-123.
• [33] M.-C. Heydemann, J.-C. Meyer, J. Opatrny, D. Sotteau, Forwarding indices of k-connected graphs, Discrete Appl. Math. 37/38 (1992), 287-296.
• [34] M.-C. Heydemann, J.-C. Meyer, J. Opatrny, D. Sotteau, Realizable values of the forwarding index, Proc. of the 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1989, Congressus Numerantium 74 (1990), 163-172.
• [35] M.-C. Heydemann, J.-C. Meyer, D. Sotteau, J. Opatrny, Forwarding indices of consistent routings and their complexity, Networks 24 (1994) 2, 75-82.
• [36] X.-M. Hou, M. Xu, J.-M. Xu, Forwarding indices of folded n-cubes, Discrete Appl. Math. 145 (2005) 3, 490-492.
• [37] X.-M. Hou, J.-M. Xu, M. Xu, The forwarding index of wrapped btterfly networks, Networks 53 (2009) 4, 329-333.
• [38] T.C. Hu, Integer Programming and Network Flows, Addison Wesley, Reading, MA, 1969.
• [39] A. Kosowski, Forwarding and optical indices of a graph, Discrete Appl. Math. 157 (2) (2009), 321-329.
• [40] E.L. Lawler, Combinatorial optimization: Networks and Matroids, Holt, Rinehart and Winston, New York, 1976.
• [41] Y. Manoussakis, Z. Tuza, Optimal routings in communication networks with linearly bounded forwarding index, Networks 28 (1996) 4, 177-180.
• [42] Y. Manoussakis, Z. Tuza, The forwarding index of directed networks, Discrete Appl. Math. 68 (1996) 3, 279-291.
• [43] J. Manuch, L. Stacho, On f-wise arc forwarding index and wavelength allocations in faulty alloptical hypercubes, Theor. Inform. Appl. 37 (2003), 255-270.
• [44] B. Mohar, Isoperimetric numbers of graphs I, J. Combin. Theory Ser. B 47 (1989), 274-291.
• [45] J.-G. Qian, F.-J. Zhang, Expanding and forwarding parameters of product graphs, Discrete Appl. Math. 136 (2004), 63-82.
• [46] P. Rużićka, D. Stefankovic, On the complexity of multi-dimensional interval routing schemes, Theoret. Comput. Sci. 245 (2000), 255-280.
• [47] R. Saad, Complexity of the forwarding index problem, SIAM J. Discrete Math. 6 (1993) 3, 418-427.
• [48] H. Schroer, O. Syora, I. Vrt'o, Optical all-to-all communication for some product graphs, Proc. 24th Seminar on Current Trends in Theory and Practice of Informatics, SOFSEM'97, LNCS, vol. 1338, 1997, 547-554.
• [49] S. Shim, J. Siran, J. Zerovnik, Counterexamples to the uniform shortest path routing conjecture for vertex-transitive graphs, Discrete Appl. Math. 119 (2002), 281-286.
• [50] F. Shahrokhi, L.A. Szekely, Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem, International Workshop on Graph-Theoretic Concepts in Computer Science, Smolenice Castle, 1998, Discrete Appl. Math. 108 (2001) 1-2, 175-191.
• [51] P. Sole, The edge-forwarding index of orbital regular graphs, Discrete Math. 130 (1994), 171-176.
• [52] P. Sole, Expanding and forwarding, Discrete Appl. Math. 58 (1995) 1, 67-78.
• [53] Y. Teranishi, Laplacian spectra and invariants of graphs, Discrete Math. 257 (2002), 183-189.
• [54] A. Thomson, S.-M. Zhou, Sanming Gossiping and routing in undirected triple-loop networks, Networks 55 (2010) 4, 341-349.
• [55] O. Togni, Optical all-to-all communication in inflated networks, Proc. of the 5th Annual International Workshop on Graph-Theoretic Concepts in Computer Science, WG'98, LNCS, vol. 1517, 1998, 78-87.
• [56] I. Vrt'o, Two remarks on "Expanding and forwarding" by P. Sole, Discrete Appl. Math. 58 (1995) 1, 85-89.
• [57] Y. Wang, One class of valency-4 Frobenius graphs, Advances in Mathematics (China) 36 (2007) 1, 115-118.
• [58] Y. Wang, A family of tetravalent Frobenius graphs, Ars Combin. 92 (2009), 131-136.
• [59] Y. Wang, X.-G. Fang, D.F. Hsu, On the edge-forwarding indices of Frobenius graphs, Acta Math. Sin. 22 (2006) 6, 1735-1744.
• [60] J.-M. Xu, Toplogical Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, Dordrecht/Boston/London, 2001.
• [61] J.-M. Xu, Thoery and Application of Graphs, Kluwer Academic Publishers, Dordrecht/Boston/London, 2003.
• [62] J.-M. Xu, M. Xu, X.-M. Hou, Forwarding indices of Cartesian product graphs, Taiwanese J. Math. 10 (2006) 5, 1305-1315.
• [63] J.-M. Xu, T. Zhou, Y. Du, J. Yan, A new upper bound on forwarding index of graphs, Ars Combin. 83 (2007), 289-293.
• [64] M. Xu, X.-J. Chen, X.-D. Hu, On the restricted forwarding index problem in communication networks, Comput. Math. Appl. 53 (2007), 1633-1643.
• [65] M. Xu, X.-M. Hou, J.-M. Xu, The proof of a conjecture of Bouabdallah and Sotteau, Networks 44 (2004) 4, 292-296.
• [66] M. Xu, J.-M. Xu, The forwarding indices of augmented cubes, Inform. Process. Lett. 101 (2007) 5, 185-189.
• [67] M. Xu, J.-M. Xu, X.-M. Hou, On edge-forwarding index of graphs with degree restriction, J. China Univ. Sci. Tech 35 (2005) 6, 732-737.
• [68] M. Xu, J.-M. Xu, L. Sun, The forwarding index of the circulant networks, Journal of Mathematics 27 (2007) 6, 621-629.
• [69] J. Yan, J.-M. Xu, C. Yang, Forwarding index of cube-connected cycles, Discrete Appl. Math. 157 (2009) 1, 1-7.
• [70] J.-J. Yuan, S.-M. Zhou, Polynomial time solvability of the weighted ring arc-loading problem with integer spitting, J. Interconnection Networks 5 (2004) 2, 193-200.
• [71] M.-J. Zhou, M. Xu, J.-M. Xu, T. Zhou, Forwarding indices of'3-connected and Z-regular graphs, J. China Univ. Sci. Tech. 38 (2008) 5, 456-459, 495.
• [72] S.-M. Zhou, A class of arc-transitive Gayley graphs as models for interconnection networks, SIAM J. Discrete Math. 23 (2009) 2, 694-714.