nach oben

The Journal of Supercomputing

Erschienen in:

24.02.2017

A linear-time algorithm for finding Hamiltonian (s, t)-paths in odd-sized rectangular grid graphs with a rectangular hole

verfasst von: Fatemeh Keshavarz-Kohjerdi, Alireza Bagheri

Erschienen in: The Journal of Supercomputing | Ausgabe 9/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.

Vorheriger Artikel Cloudlet dynamic server selection policy for mobile task off-loading in mobile cloud computing using soft computing techniques

Nächster Artikel A simple token-based algorithm for the mutual exclusion problem in distributed systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Abdullah M, Abuelrub E, Mahafzah B (2011) The chained-cubic tree interconnection network. Int Arab J Inf Technol 8(3):334–343

Afrati FN (1994) The Hamilton circuit problem on grids. Theor Inform Appl 28(6):567–582MathSciNetCrossRefMATH

Arikati SR, Rangan CP (1990) Linear algorithm for optimal path cover problem on interval graphs. Inf Process Lett 35:149–153MathSciNetCrossRefMATH

Bhandarkar SM, Arabnia HR (1997) Parallel computer vision on a reconfigurable multiprocessor network. IEEE Trans Parallel Distrib Syst 8(3):292–309CrossRef

Bertossi AA (1983) Finding Hamiltonian circuits in proper interval graphs. Inf Process Lett 17(2):97–101MathSciNetCrossRefMATH

Chen SD, Shen H, Topor R (2002) An efficient algorithm for constructing Hamiltonian paths in meshes. Parallel Comput 28(9):1293–1305MathSciNetCrossRefMATH

Chen YC, Huang YZ, Hsu LH, Tan JJM (2010) A family of Hamiltonian and Hamiltonian connected graphs with fault tolerance. J Supercomput 54:229–238CrossRef

Damasachke P (1989) The Hamiltonian circuit problem for circle graphs is NP-complete. Inf Process Lett 32:1–2MathSciNetCrossRef

Damaschke P, Deogun JS, Kratsch D, Steiner G (1991) Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm. Order 8(4):383–391MathSciNetCrossRefMATH

10.

Du L (2010) A polynomial time algorithm for Hamiltonian cycle (path). In: Proceedings of the International MultiConference of Engineers and Computer Scientists, IMECS I. pp 17–19

11.

Felsner S, Liotta G, Wismath S (2003) Straight-line drawings on restricted integer grids in two and three dimensions. J Graph Algorithms Appl 7(4):363–398MathSciNetCrossRefMATH

12.

Fu JS (2008) Hamiltonian connectivity of the WK-recursive with faulty nodes. Inf Sci 178:2573–2584MathSciNetCrossRefMATH

13.

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San FranciscoMATH

14.

Garey MR, Johnson DS, Tarjan RE (1976) The planar Hamiltonian circuit problem is NP-complete. SIAM J Comput 5:704–714MathSciNetCrossRefMATH

15.

Gorbenko A, Popov V, Sheka A (2012) Localization on discrete grid graphs. In: He X, Hua E, Lin Y, Liu X (eds) Computer, informatics, cybernetics and applications, lecture notes in electrical engineering. pp 971–978

16.

Gould RJ (2003) Advances on the Hamiltonian problem: a survey. Graphs Comb 19(1):7–52MathSciNetCrossRefMATH

17.

Gordon VS, Orlovich YL, Werne F (2008) Hamiltonian properties of triangular grid graphs. Discrete Math 308(24):6166–6188MathSciNetCrossRefMATH

18.

Hamada K (2013) A picturesque maze generation algorithm with any given endpoints. J Inf Process 21(3):393–397

19.

Hsieh SY, Kuo CN (2007) Hamiltonian-connectivity and strongly Hamiltonian-laceability of folded hypercubes. Comput Math Appl 53:1040–1044MathSciNetCrossRefMATH

20.

Hung RW (2016) Hamiltonian cycles in linear-convex supergrid graphs. Discrete Appl Math 211:99–112MathSciNetCrossRefMATH

21.

Hung RW (2012) Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes. IAENG Int J Comput Sci 39(1):42–49

22.

Icking C, Kamphans T, Klein R, Langetepe E (2005) Exploring simple grid polygons. In: Proceedings of 11th Annual International Computing and Combinatorics Conference, COCOON. pp 524–533

23.

Islam K, Meijer H, Rodriguez YN, Rappaport D, Xiao H (2007) Hamiltonian circuits in hexagonal grid graphs. In: Proceedings of 19th Canadian Conference of Computational Geometry, CCCG’97. pp 85–88

24.

Itai A, Papadimitriou CH, Szwarcfiter JL (1982) Hamiltonian paths in grid graphs. SIAM J Comput 11(4):676–686MathSciNetCrossRefMATH

25.

Keshavarz-Kohjerdi F, Bagheri A (2012) Hamiltonian paths in some classes of grid graphs. J Appl Math. doi:10.1155/2012/475087 MathSciNetMATH

26.

Keshavarz-Kohjerdi F, Bagheri A, Asgharian-Sardroud A (2012) A linear-time algorithm for the longest path problem in rectangular grid graphs. Discrete Appl Math 160(3):210–217MathSciNetCrossRefMATH

27.

Keshavarz-Kohjerdi F, Bagheri A (2013) A parallel algorithm for the longest path problem in rectangular grid graphs. J Supercomput 65:723–741CrossRef

28.

Keshavarz-Kohjerdi F, Bagheri A (2016) Hamiltonian paths in \(L\)-shaped grid graphs. Theor Comput Sci 621:37–56MathSciNetCrossRefMATH

29.

Keshavarz-Kohjerdi F, Bagheri A (2016) Hamiltonian paths in \(C\)-shaped grid graphs. arXiv:1602.07407

30.

Lenhart W, Umans C (1997) Hamiltonian cycles in solid grid graphs. In: Proceedings of 38th Annual Symposium on Foundations of Computer Science, FOCS ’97. pp 496–505

31.

Li Y, Peng S, Chu W (2009) Hamiltonian connectedness of recursive dual-net. In: Proceedings of the 9th IEEE International Conference on Computer and Information Technology, CIT09, vol 1. pp 203–208

32.

Luccio F, Mugnia C (1978) Hamiltonian paths on a rectangular chessboard. In: Proceedings of 16th Annual Allerton Conference, pp 161–173

33.

Myers BR (1981) Enumeration of tours in Hamiltonian rectangular lattice graphs. Math Mag 54:19–23MathSciNetCrossRefMATH

34.

Park CD, Chwa KY (2004) Hamiltonian properties on the class of hypercube-like networks. Inf Process Lett 91:11–17MathSciNetCrossRefMATH

35.

Rahman MS, Kaykobad M (2005) On Hamiltonian cycles and Hamiltonian paths. Inf Process Lett 94(1):37–41MathSciNetCrossRefMATH

36.

Ray SS (2013) Graph theory with algorithms and applications: in applied science and technology. Springer, BerlinMATH

37.

Salman ANM, Broersma HJ, Baskoro ET (2003) Spanning 2-connected subgraphs in alphabet graphs, special classes of grid graphs. J Autom Lang Comb 8(4):675–681MathSciNetMATH

38.

Srinivasa Rao ASR, Tomleyc F, Blakec D (2015) Understanding chicken walks on \(n \times n\) grid: Hamiltonian paths, discrete dynamics, and rectifiable paths. Math Methods Appl Sci 38(15):3346–3358MathSciNetCrossRefMATH

39.

Zamfirescu C, Zamfirescu T (1992) Hamiltonian properties of grid graphs. SIAM J Discrete Math 5(4):564–570MathSciNetCrossRefMATH

40.

Zhang WQ, Liu YJ (2011) Approximating the longest paths in grid graphs. Theor Comput Sci 412(39):5340–5350MathSciNetCrossRefMATH

Titel: A linear-time algorithm for finding Hamiltonian (s, t)-paths in odd-sized rectangular grid graphs with a rectangular hole
verfasst von: Fatemeh Keshavarz-Kohjerdi
Alireza Bagheri
Publikationsdatum: 24.02.2017
Verlag: Springer US
Erschienen in: The Journal of Supercomputing / Ausgabe 9/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI: https://doi.org/10.1007/s11227-017-1984-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 9/2017

Optimization of data-intensive workflows in stream-based data processing models

Limited contiguous processor allocation mechanism in the mesh-connected multiprocessors using compaction

MAP-SDN: a metaheuristic assignment and provisioning SDN framework for cloud datacenters

Profile-based dynamic application assignment with a repairing genetic algorithm for greener data centers

Cloudlet dynamic server selection policy for mobile task off-loading in mobile cloud computing using soft computing techniques

Cloud computing burst system (CCBS): for exa-scale computing system