Fault tolerance of hypercube like networks: spanning laceability under edge faults. (English) Zbl 1461.68040
Summary: Given two vertices \(u\) and \(v\) in a connected undirected graph \(G\), a \(w \ast\)-container \(C(u, v)\) is a set of \(w\) internally vertex disjoint paths between \(u\) and \(v\) spanning all the vertices in \(G\). A bipartite graph \(G\) is \(w^\ast\)-laceable if there exists a \(w^\ast\)-container between any two vertices belonging to different partitions of \(G\). In
[J. X. Fan and L. Q. He, “BC interconnection networks and their properties”, Chin. J. Comput. 26, No. 1, 84–90 (2003);
A. S. Vaidya et al., “A class of hypercube-like networks”, in: Proceedings of the 5th IEEE symposium on parallel and distributed processing, SPDP’93. Los Alamitos, CA: IEEE Computer Society. 800–803 (1993; doi:10.1109/SPDP.1993.395450)]
a class \(B_n^\prime\) of bipartite graphs called hypercube-like bipartite networks was defined. In
[Theor. Comput. Sci. 381, No. 1–3, 218–229 (2007; Zbl 1206.05060)], C.-K. Lin et al.
showed that every graph in \(B_n^\prime\) is \(w^\ast\)-laceable for every \(1 \leq w \leq n\). We define a graph is \(f\)-edge fault tolerant \(w^\ast\)-laceable if \(G - F\) is \(w^\ast\)-laceable for any arbitrary subset \(F\) of edges of \(G\) with \(|F| \leq f\). In this paper we show that every graph in \(B_n^\prime\) is \(f\)-edge-fault tolerant \(w^\ast \)-laceable for every \(0 \leq f \leq n - 2\) and \(1 \leq w \leq n - f\) which generalize Lin’s result. We also give generalization of two other results in
[Lin et al., loc. cit.;
C.-D. Park and K.-Y. Chwa, Inf. Process. Lett. 91, No. 1, 11–17 (2004; Zbl 1178.68043)].
MSC:
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 05C40 | Connectivity |
| 68R10 | Graph theory (including graph drawing) in computer science |
Keywords:
\(w^\ast\)-connectivity; \(w^\ast\)-laceability; hypercube-like network; fault tolerance; network survivabilityReferences:
| [1] | Abraham, S.; Padmanabhan, K., The twisted cube topology for multiprocessors: a study in network asymmetry, J. Parallel Distrib. Comput., 13, 104-110 (1991) |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), The Macmillan Press Ltd.: The Macmillan Press Ltd. New York · Zbl 1226.05083 |
| [3] | Chlamtac, I.; Ganz, A.; Karmi, G., Lightpath communications: an approach to high bandwidth optical WDM, IEEE Trans. Commun., 40, 7, 1171-1182 (1992) |
| [4] | Choudhum, S. A.; Lavanya, S.; Sunitha, V., Disjoint paths in hypercubes with prescribed origins and lengths, Int. J. Comput. Math., 87, 1692-1708 (2010) · Zbl 1221.05216 |
| [5] | Cull, P.; Larson, S. M., Möbius cubes, IEEE Trans. Comput., 44, 5, 647-659 (1995) · Zbl 1041.68522 |
| [6] | Dirac, G. A., In abstrakten Graphen vorhandene vollstandige 4-Graphen und ihre Unterteilungen, Math. Nachr., 22, 61-85 (1960) · Zbl 0096.17903 |
| [7] | Efe, K., The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distrib. Syst., 3, 5, 513-524 (1992) |
| [8] | Fan, J. X.; He, L. Q., BC interconnection networks and their properties, Chinese J. Comput., 26, 1, 84-90 (2003) |
| [9] | Gu, Q. P.; Peng, S., An efficient algorithm for k-pairwise disjoint paths problem in hypercubes, J. Parallel Distrib. Comput., 60, 764-774 (2000) · Zbl 0957.68006 |
| [10] | Hsieh, S.-Y.; Chen, G.-H.; Ho, C.-W., Fault-free Hamiltonian cycles in faulty arrangement graphs, IEEE Trans. Parallel Distrib. Syst., 10, 3, 223-237 (1999) |
| [11] | Hsieh, S.-Y.; Chen, G.-H.; Ho, C.-W., Hamiltonian-laceability of star graphs, Networks, Int. J., 36, 4, 225-232 (2000) · Zbl 0968.05051 |
| [12] | Hsu, D. F., On container width and length in graphs, groups and networks, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., E77-A, 4, 668-680 (1994) |
| [13] | Hsu, H.-C.; Lin, C.-K.; Hung, H.-M.; Hsu, L.-H., The spanning connectivity of the \((n, k)\)-star graphs, Int. J. Found. Comput. Sci., 17, 2, 415-434 (2006) · Zbl 1103.68097 |
| [14] | Huang, P.-Y.; Hsu, L.-H., The spanning connectivity of line graphs, Appl. Math. Lett., 24, 9, 1614-1617 (2011) · Zbl 1219.05083 |
| [15] | Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory, 44, 559-611 (1998) · Zbl 1105.94342 |
| [16] | Kurant, M.; Thiran, P., Survivable mapping algorithm by ring trimming (SMART) for large IP-over-WDM networks, Broadnets (2004) |
| [17] | Kurant, M.; Thiran, P., On survivable routing of mesh topologies in IP-over-WDM networks, (Proc. of IEEE Conference on Computer Communications (2005)) |
| [18] | Li, J.; Liu, D.; Yuan, J., The super spanning connectivity and super spanning laceability of tori with faulty elements, Int. J. Found. Comput. Sci., 24, 6, 921-939 (2013) · Zbl 1310.68026 |
| [19] | Li, P.; Xu, M., The super spanning connectivity of arrangement graphs, Int. J. Found. Comput. Sci., 28, 8, 1047-1072 (2017) · Zbl 1390.05114 |
| [20] | Lin, C.-K.; Ho, T.-Y.; Tan, J. J.M.; Hsu, L.-J., Super spanning connectivity of augmented cubes, Ars Comb., 104, 161-177 (2012) · Zbl 1274.05269 |
| [21] | Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., On the spanning connectivity of graphs, Discrete Math., 307, 2, 285-289 (2007) · Zbl 1177.05064 |
| [22] | Lin, C.-K.; Tan, J. J.M.; Hsu, D. F.; Hsu, L.-H., On the spanning connectivity and spanning laceability of hypercube-like networks, Theor. Comput. Sci., 381, 1-3, 218-229 (2007) · Zbl 1206.05060 |
| [23] | Lin, C.-K.; Tan, J. J.M.; Hsu, D. F.; Hsu, L.-H., On the spanning fan-connectivity of graphs, Discrete Appl. Math., 157, 7, 1342-1348 (2009) · Zbl 1183.05045 |
| [24] | Ma, M., The spanning connectivity of folded hypercubes, Inf. Sci., 180, 17, 3373-3379 (2010) · Zbl 1205.68046 |
| [25] | Modiano, E.; Narula-Tam, A., Survivable lightpath routing: a new approach to the design of WDM-based networks, IEEE J. Sel. Areas Commun., 20, 800-809 (2002) |
| [26] | Park, J. H., One-to-many disjoint path covers in a graph with faulty elements, (Lecture Notes in Comput. Sci., vol. 3106 (2004)), 392-401 · Zbl 1091.68080 |
| [27] | Park, J. H.; Chwa, K. Y., Hamiltonian properties on the class of hypercube-like networks, Inf. Process. Lett., 91, 11-17 (2004) · Zbl 1178.68043 |
| [28] | Park, J. H.; Kim, H. C.; Lim, H. S., Many-to-Many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Trans. Parallel Distrib. Syst., 17, 3, 227-240 (2006) |
| [29] | Shih, L. M.; Chiang, C. F.; Hsu, L. H.; Tan, J. J.M., Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inf. Process. Lett., 106, 64-69 (2008) · Zbl 1186.68033 |
| [30] | Thulasiraman, K.; Arumugam, S.; Brandstädt, A.; Nishizeke, T., Handbook of Graph Theory, Combinatorial Optimization, and Algorithms (2015), CRC Press |
| [31] | Thulasiraman, K.; Javed, M.; Xue, G., Circuits/cutsets duality and a unified algorithmic framework for survivable logical topology design in IP-over-WDM optical networks, (Proc. of IEEE Conference on Computer Communications (2009)) |
| [32] | Thulasiraman, K.; Javed, M.; Xue, G., Primal meets dual: a generalized theory of logical topology survivability in IP-over-WDM optical networks, (Proc. of the 2nd International Conference on Communication Systems and Networks (2009)), 128-137 |
| [33] | Vaidya, A. S.; Rao, P. S.N.; Shankar, S. R., A class of hypercube-like networks, (Proc. of IEEE Symposium on Parallel and Distributed Processing (1993)), 800-803 |
| [34] | Wang, J.-J.; Hsu, L.-H., On the spanning connectivity of the generalized Petersen graphs \(P(n, 3)\), Discrete Math., 341, 3, 672-690 (2018) · Zbl 1378.05110 |
| [35] | Xiao, Y.; Hadjicostis, C.; Thulasiraman, K., The d-identifying codes problem for vertex identification in graphs: probabilistic analysis and an approximation algorithm, (Proc. of 12th Annual International Computing and Combinatorics Conference. Proc. of 12th Annual International Computing and Combinatorics Conference, Taipei (August 2006)) · Zbl 1162.05363 |
| [36] | Xu, J. M.; Ma, M. J.; Du, Z. Z., Edge-fault-tolerant properties of hypercubes and folded hypercubes, Australas. J. Comb., 35, 7-16 (2006) · Zbl 1106.68088 |
| [37] | Xu, M.; Thulasiraman, K.; Hu, X. D., Identifying codes of cycles of odd orders, Eur. J. Comb., 1717-1720 (2008) · Zbl 1145.94020 |
| [38] | You, L.; Fan, J.; Han, Y., Super spanning connectivity on WK-recursive networks, Theor. Comput. Sci., 713, 42-55 (2018) · Zbl 1386.68016 |
| [39] | Zhou, Z.; Lin, T.; Thulasiraman, K.; Xue, G., Novel survivable logical topology routing in an IP over WDM optical network based on the logical protection spanning tree set, IEEE/ACM Trans. Netw., 25, 1673-1685 (2017) |
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.
