×

zbMATH — the first resource for mathematics

The Hamiltonian connectivity of rectangular supergrid graphs. (English) Zbl 1387.05140
Summary: A Hamiltonian path of a graph is a simple path which visits each vertex of the graph exactly once. The Hamiltonian path problem is to determine whether a graph contains a Hamiltonian path. A graph is called Hamiltonian connected if there exists a Hamiltonian path between any two distinct vertices. In this paper, we will study the Hamiltonian connectivity of rectangular supergrid graphs. Supergrid graphs were first introduced by us and include grid graphs and triangular grid graphs as subgraphs. The Hamiltonian path problem for grid graphs and triangular grid graphs was known to be NP-complete. Recently, we have proved that the Hamiltonian path problem for supergrid graphs is also NP-complete. The Hamiltonian paths on supergrid graphs can be applied to compute the stitching traces of computer sewing machines. Rectangular supergrid graphs form a popular subclass of supergrid graphs, and they have strong structure. In this paper, we provide a constructive proof to show that rectangular supergrid graphs are Hamiltonian connected except one trivial forbidden condition. Based on the constructive proof, we present a linear-time algorithm to construct a longest path between any two given vertices in a rectangular supergrid graph.

MSC:
05C45 Eulerian and Hamiltonian graphs
05C40 Connectivity
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ascheuer, N., Hamiltonian Path Problems in the 0n-Line Optimization of Flexible Manufacturing Systems, Tech. Rep. TR 96-3, (1996), Konrad-Zuse-Zentrum für Informationstechnik Berlin
[2] O’Callaghan, J. F., Computing the perceptual boundaries of dot patterns, Comput. Graphics Image Process., 3, 141-162, (1974)
[3] Bermond, J. C., Hamiltonian graphs, (Beinke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, (1978), Academic Press New York) · Zbl 0329.05113
[4] Preperata, F. P.; Shamos, M. I., Computational Geometry: An Introduction, (1985), Springer New York
[5] G.T. Toussaint, Pattern recognition and geometrical complexity, in: Proceedings of the 5th International Conference on Pattern Recognition, Miami Beach, 1980, pp. 1324-1347.
[6] Grebinski, V.; Kucherov, G., Reconstructing a Hamiltonian cycle by querying the graph: application to DNA physical mapping, Discrete Appl. Math., 88, 147-165, (1998) · Zbl 0936.68107
[7] M. Ebrahimi, M. Daneshtalab, J. Plosila, Fault-tolerant routing algorithm for 3D NoC using hamiltonian path strategy, in: Proceedings of the Conference on Design, Automation and Test in Europe, DATE’2013, 2013, pp. 1601-1604.
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[9] Johnson, D. S., The NP-complete column: an ongoing guide, J. Algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[10] Krishnamoorthy, M. S., An NP-hard problem in bipartite graphs, SIGACT News, 7, 26, (1976)
[11] Golumbic, M. C., (Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol. 57, (2004), Elsevier) · Zbl 1050.05002
[12] Damaschke, P., The Hamiltonian circuit problem for circle graphs is NP-complete, Inform. Process. Lett., 32, 1-2, (1989) · Zbl 0681.68062
[13] Bertossi, A. A.; Bonuccelli, M. A., Hamiltonian circuits in interval graph generalizations, Inform. Process. Lett., 23, 195-200, (1986) · Zbl 0627.68056
[14] Itai, A.; Papadimitriou, C. H.; Szwarcfiter, J. L., Hamiltonian paths in grid graphs, SIAM J. Comput., 11, 676-686, (1982) · Zbl 0506.05043
[15] Gordon, V. S.; Orlovich, Y. L.; Werner, F., Hamiltonin properties of triangular grid graphs, Discrete Math., 308, 6166-6188, (2008) · Zbl 1158.05040
[16] Hung, R. W.; Yao, C. C.; Chan, S. J., The Hamiltonian properties of supergrid graphs, Theoret. Comput. Sci., 602, 132-148, (2015) · Zbl 1330.05093
[17] Fu, J. S., Hamiltonian connectivity of the WK-recursive with faulty nodes, Inform. Sci., 178, 2573-2584, (2008) · Zbl 1183.68097
[18] Y. Li, S. Peng, W. Chu, Hamiltonian connectedness of recursive dual-net, in: Proceedings of the 9th IEEE International Conference on Computer and Information Technology, CIT’2009, vol. 1, 2009 pp. 203-208.
[19] Chen, G. H.; Fu, J. S.; Fang, J. F., Hypercomplete: a pancyclic recursive topology for large scale distributed multicomputer systems, Networks, 35, 56-69, (2000) · Zbl 0938.90066
[20] Jwo, J.; Lakshmivarahan, S.; Dhall, S. K., A new class of interconnection networks based on the alternating group, Networks, 23, 315-326, (1993) · Zbl 0774.90031
[21] Lo, R. S.; Chen, G. H., Embedding Hamiltonian paths in faulty arrangement graphs with the backtracking method, IEEE Trans. Parallel Distrib. Syst., 12, 209-222, (2001)
[22] Hung, R. W., Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes, IAENG Int. J. Comput. Sci., 39, 42-49, (2012)
[23] Huang, C. H.; Fang, J. F., The pancyclicity and the Hamiltonian-connectivity of the generalized base-\(b\) hypercube, Comput. Electr. Eng., 34, 263-269, (2008) · Zbl 1147.68416
[24] Park, C. D.; Chwa, K. Y., Hamiltonian properties on the class of hypercube-like networks, Inform. Process. Lett., 91, 11-17, (2004) · Zbl 1178.68043
[25] Huang, W. T.; Tan, J. J.M.; Huang, C. N.; Hsu, L. H., Fault-tolerant Hamiltonicity of twisted cubes, J. Parallel Distrib. Comput., 62, 591-604, (2002) · Zbl 1008.68017
[26] W.T. Huang, M.Y. Lin, J.M. Tan, L.H. Hsu, Fault-tolerant ring embedding in faulty crossed cubes, in: Proceedings of World Multiconference on Systemics, Cybernetics, and Informatics, SCI’2000, 2000, pp. 97-102.
[27] Chen, Y. C.; Tsai, C. H.; Hsu, L. H.; Tan, J. J.M., On some super fault-tolerant Hamiltonian graphs, Appl. Math. Comput., 148, 729-741, (2004) · Zbl 1032.05078
[28] Hsieh, S. Y.; Kuo, C. N., Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes, Comput. Math. Appl., 53, 1040-1044, (2007) · Zbl 1149.68409
[29] M. Liu, H.M. Liu, The edge-fault-tolerant Hamiltonian connectivity of enhanced hypercube, in: International Conference on Network Computing and Information Security, NCIS’2011, vol. 2, 2011, pp. 103-107.
[30] Bulterman, R. W.; van der Sommen, F. W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A. J.M.; Feijen, W. H.J., On computing a longest path in a tree, Inform. Process. Lett., 81, 93-96, (2001) · Zbl 1032.68671
[31] Uehara, R.; Uno, Y., On computing longest paths in small graph classes, Internat. J. Found Comput. Sci., 18, 911-930, (2007) · Zbl 1202.68291
[32] Ioannidou, K.; Mertzios, G. B.; Nikolopoulos, S. D., The longest path problem has a polynomial solution on interval graphs, Algorithmica, 61, 320-341, (2011) · Zbl 1236.05114
[33] Mertzios, G. B.; Corneil, D. G., A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM J. Discrete Math., 26, 940-963, (2012) · Zbl 1256.05237
[34] Mertzios, G. B.; Bezáková, I., Computing and counting longest paths on circular-arc graphs in polynomial time, Discrete Appl. Math., 164, 383-399, (2014) · Zbl 1288.05137
[35] Keshavarz-Kohjerdi, F.; Bagheri, A.; Asgharian-Sardroud, A., A linear-time algorithm for the longest path problem in rectangular grid graphs, Discrete Appl. Math., 160, 210-217, (2012) · Zbl 1237.05115
[36] Zamfirescu, C.; Zamfirescu, T., Hamiltonian properties of grid graphs, SIAM J. Discrete Math., 5, 564-570, (1992) · Zbl 0770.05073
[37] Chen, S. D.; Shen, H.; Topor, R., An efficient algorithm for constructing Hamiltonian paths in meshes, Parallel Comput., 28, 1293-1305, (2002) · Zbl 0999.68253
[38] W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 496-505.
[39] Salman, A. N.M., Contributions to Graph Theory, (2005), University of Twente, (Ph.D. thesis)
[40] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in some classes of grid graphs, J. Appl. Math., (2012), article no. 475087 · Zbl 1245.05081
[41] Keshavarz-Kohjerdi, F.; Bagheri, A., An efficient parallel algorithm for the longest path problem in meshes, J. Supercomput., 65, 723-741, (2013)
[42] Keshavarz-Kohjerdi, F.; Bagheri, A., Hamiltonian paths in \(L\)-shaped grid graphs, Theoret. Comput. Sci., 621, 37-56, (2016) · Zbl 1335.05100
[43] Reay, J. R.; Zamfirescu, T., Hamiltonian cycles in \(T\)-graphs, Discrete Comput. Geom., 24, 497-502, (2000) · Zbl 0953.05040
[44] K. Islam, H. Meijer, Y. Núũez, D. Rappaport, H. Xiao, Hamiltonian cycles in hexagonal grid graphs, in: Proceedings of the 19th Canadian Conference on Computational Geometry, CCCG’2007, 2009, pp. 85-88.
[45] Zhang, W. Q.; Liu, Y. J., Approximating the longest paths in grid graphs, Theoret. Comput. Sci., 412, 5340-5350, (2011) · Zbl 1222.68089
[46] Asgharian-Sardroud, A.; Bagheri, A., An approximation algorithm for the longest cycle problem in solid grid graphs, Discrete Appl. Math., 204, 6-12, (2016) · Zbl 1333.05091
[47] Asgharian-Sardroud, A.; Bagheri, A., An approximation algorithm for the longest path problem in solid grid graphs, Optim. Methods Softw., 31, 479-493, (2016) · Zbl 1357.68297
[48] Hung, R. W., Hamiltonian cycles in linear-convex supergrid graphs, Discrete Appl. Math., 211, 99-112, (2016) · Zbl 1348.05117
[49] Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications, (1976), Macmillan Press London · Zbl 1134.05001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.