Disjoint path covers with path length constraints in restricted hypercube-like graphs. (English) Zbl 1372.68215
Summary: A disjoint path cover of a graph is a set of pairwise vertex-disjoint paths that altogether cover every vertex of the graph. In this paper, we prove that given \(k\) sources, \(s_1,\ldots, s_k\), in an \(m\)-dimensional restricted hypercube-like graph with a set \(F\) of faults (vertices and/or edges), associated with \(k\) positive integers, \(l_1,\ldots,l_k\), whose sum is equal to the number of fault-free vertices, there exists a disjoint path cover composed of \(k\) fault-free paths, each of whose paths starts at \(s_i\) and contains \(l_i\) vertices for \(i \in \{1, \ldots, k \}\), provided \(| F | + k \leq m - 1\). The bound, \(m - 1\), on \(| F | + k\) is the best possible.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
hypercube-like graph; disjoint path cover; path partition; prescribed sources; prescribed path lengths; fault tolerance; interconnection networkReferences:
| [1] | Arikati, S. R.; Rangan, C. P., Linear algorithm for optimal path cover problem on interval graphs, Inf. Process. Lett., 35, 3, 149-153 (1990) · Zbl 0697.68048 |
| [2] | Asdre, K.; Nikolopoulos, S. D., The 1-fixed-endpoint path cover problem is polynomial on interval graphs, Algorithmica, 58, 3, 679-710 (2010) · Zbl 1200.05212 |
| [3] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001 |
| [4] | Chedid, F. B., On the generalized twisted cube, Inf. Process. Lett., 55, 49-52 (1995) · Zbl 0875.68142 |
| [5] | Chen, X.-B., Many-to-many disjoint paths in faulty hypercubes, Inf. Sci., 179, 18, 3110-3115 (2009) · Zbl 1193.68050 |
| [6] | Chen, X.-B., Paired many-to-many disjoint path covers of the hypercubes, Inf. Sci., 236, 218-223 (2013) · Zbl 1284.05274 |
| [7] | Choudum, S. A.; Lavanya, S.; Sunitha, V., Disjoint paths in hypercubes with prescribed origins and lengths, Int. J. Comput. Math., 87, 8, 1692-1708 (2010) · Zbl 1221.05216 |
| [8] | Cull, P.; Larson, S., The Möbius cubes, (Proc. of the 6th IEEE Distributed Memory Computing Conf. (1991)), 699-702 |
| [9] | Dvořák, T.; Gregor, P., Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math., 22, 4, 1448-1461 (2008) · Zbl 1187.05056 |
| [10] | Dvořák, T.; Gregor, P.; Koubek, V., Generalized Gray codes with prescribed ends, Theor. Comput. Sci., 668, 70-94 (2017) · Zbl 1367.94402 |
| [11] | Efe, K., A variation on the hypercube with lower diameter, IEEE Trans. Comput., 40, 11, 1312-1316 (1991) |
| [12] | Efe, K., The crossed cube architecture for parallel computation, IEEE Trans. Parallel Distrib. Syst., 3, 5, 513-524 (1992) |
| [13] | Fan, J.; Jia, X.; Cheng, B.; Yu, J., An efficient fault-tolerant routing algorithm in bijective connection networks with restricted faulty edges, Theor. Comput. Sci., 412, 3440-3450 (2011) · Zbl 1216.68055 |
| [14] | Fan, J.; Jia, X.; Liu, X.; Zhang, S.; Yu, J., Efficient unicast in bijective connection networks with the restricted faulty node set, Inf. Sci., 181, 2303-2315 (2011) · Zbl 1216.68056 |
| [15] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman & Co.: W.H. Freeman & Co. San Francisco · Zbl 0411.68039 |
| [16] | Gregor, P.; Dvořák, T., Path partitions of hypercubes, Inf. Process. Lett., 108, 6, 402-406 (2008) · Zbl 1191.68037 |
| [17] | Hilbers, P. A.J.; Koopman, M. R.J.; van de Snepscheut, J. L.A., The twisted cube, (Bakker, J.; Nijman, A.; Treleaven, P., PARLE: Parallel Architectures and Languages Europe, Vol. I: Parallel Architectures (1987), Springer), 152-159 |
| [18] | Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2008), CRC Press |
| [19] | Hung, R.-W.; Chang, M.-S., Finding a minimum path cover of a distance-hereditary graph in polynomial time, Discrete Appl. Math., 155, 17, 2242-2256 (2007) · Zbl 1127.05079 |
| [20] | Jo, S.; Park, J.-H.; Chwa, K. Y., Paired 2-disjoint path covers and strongly Hamiltonian laceability of bipartite hypercube-like graphs, Inf. Sci., 242, 103-112 (2013) · Zbl 1337.68210 |
| [21] | Jo, S.; Park, J.-H.; Chwa, K. Y., Paired many-to-many disjoint path covers in faulty hypercubes, Theor. Comput. Sci., 513, 1-24 (2013) · Zbl 1352.68195 |
| [22] | Kim, S.-Y.; Lee, J.-H.; Park, J.-H., Disjoint path covers in recursive circulants \(G(2^m, 4)\) with faulty elements, Theor. Comput. Sci., 412, 35, 4636-4649 (2011) · Zbl 1223.68083 |
| [23] | Kim, S.-Y.; Park, J.-H., Paired many-to-many disjoint path covers in recursive circulants \(G(2^m, 4)\), IEEE Trans. Comput., 62, 12, 2468-2475 (2013) · Zbl 1372.68211 |
| [24] | Kim, S.-Y.; Park, J.-H., Many-to-many two-disjoint path covers in restricted hypercube-like graphs, Theor. Comput. Sci., 531, 26-36 (2014) · Zbl 1359.68233 |
| [25] | Lai, P.-L.; Hsu, H.-C., The two-equal-disjoint path cover problem of matching composition network, Inf. Process. Lett., 107, 1, 18-23 (2008) · Zbl 1186.68025 |
| [26] | Lim, H.-S.; Kim, H.-C.; Park, J.-H., Ore-type degree conditions for disjoint path covers in simple graphs, Discrete Math., 339, 2, 770-779 (2016) · Zbl 1327.05276 |
| [27] | Lin, R.; Olariu, S.; Pruesse, G., An optimal path cover algorithm for cographs, Comput. Math. Appl., 30, 8, 75-83 (1995) · Zbl 0836.68086 |
| [28] | McHugh, J. A.M., Algorithmic Graph Theory (1990), Prentice Hall: Prentice Hall Englewood Cliffs, NJ · Zbl 0755.68056 |
| [29] | McSorley, J. P., Counting structures in the Möbius ladder, Discrete Math., 184, 1-3, 137-164 (1998) · Zbl 0957.05057 |
| [30] | Nebeský, L., Embedding \(m\)-quasistars into \(n\)-cubes, Czechoslov. Math. J., 38, 113, 705-712 (1988) · Zbl 0677.05021 |
| [31] | Ntafos, S. C.; Hakimi, S. L., On path cover problems in digraphs and applications to program testing, IEEE Trans. Softw. Eng., 5, 5, 520-529 (1979) · Zbl 0412.68052 |
| [32] | Park, J.-H.; Choi, J.; Lim, H.-S., Algorithms for finding disjoint path covers in unit interval graphs, Discrete Appl. Math., 205, 132-149 (2016) · Zbl 1333.05296 |
| [33] | Park, J.-H.; Chwa, K. Y., Recursive circulants and their embeddings among hypercubes, Theor. Comput. Sci., 244, 35-62 (2000) · Zbl 0945.68003 |
| [34] | Park, J.-H.; Ihm, I., Disjoint path covers in cubes of connected graphs, Discrete Math., 325, 65-73 (2014) · Zbl 1288.05145 |
| [35] | Park, J.-H.; Ihm, I., Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Discrete Appl. Math., 185, 168-191 (2015) · Zbl 1311.05092 |
| [37] | 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) |
| [38] | Park, J.-H.; Kim, H.-C.; Lim, H.-S., Many-to-many disjoint path covers in the presence of faulty elements, IEEE Trans. Comput., 58, 4, 528-540 (2009) · Zbl 1368.68090 |
| [39] | Park, J.-H.; Lim, H.-S.; Kim, H.-C., Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theor. Comput. Sci., 377, 1-3, 170-180 (2007) · Zbl 1115.68116 |
| [40] | Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 412, 35, 4513-4530 (2011) · Zbl 1223.68086 |
| [41] | Singhvi, N. K.; Ghose, K., The Mcube: a symmetrical cube based network with twisted links, (Proc. of the 9th IEEE Int. Parallel Processing Symposium (1995)), 11-16 |
| [42] | Srikant, R.; Sundaram, R.; Singh, K. S.; Rangan, C. P., Optimal path cover problem on block graphs and bipartite permutation graphs, Theor. Comput. Sci., 115, 2, 351-357 (1993) · Zbl 0774.68065 |
| [43] | Vaidya, A. S.; Rao, P. S.N.; Shankar, S. R., A class of hypercube-like networks, (Proc. of the 5th IEEE Symposium on Parallel and Distributed Processing (1993)), 800-803 |
| [44] | Wang, X.; Fan, J.; Jia, X.; Lin, C.-K., An efficient algorithm to construct disjoint path covers of DCell networks, Theor. Comput. Sci., 609, 197-210 (2016) · Zbl 1331.68159 |
| [45] | Zhang, M.; Meng, J.; Yang, W.; Tian, Y., Reliability analysis of bijective connection networks in terms of the extra edge-connectivity, Inf. Sci., 279, 374-382 (2014) · Zbl 1354.68027 |
| [46] | Zhang, S.; Wang, S., Many-to-many disjoint path covers in \(k\)-ary \(n\)-cubes, Theor. Comput. Sci., 491, 103-118 (2013) · Zbl 1277.68040 |
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.
