A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole (Q2399614): Difference between revisions

Latest revision as of 07:02, 14 July 2024

scientific article

Language	Label	Description	Also known as
English	A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole	scientific article

Statements

instance of

scholarly article

0 references

title

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

0 references

author

Fatemeh Keshavarz-Kohjerdi

0 references

Alireza Bagheri

0 references

published in

Theoretical Computer Science

0 references

publication date

24 August 2017

0 references

zbMATH Keywords

grid graph

0 references

Hamiltonian path

0 references

Hamiltonian cycle

0 references

rectangular grid graphs with a rectangular hole

0 references

NP-completeness

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/j.tcs.2017.05.031

0 references

cites work

The Hamilton circuit problem on grids

0 references

An efficient algorithm for constructing Hamiltonian paths in meshes

0 references

The Hamiltonian circuit problem for circle graphs is NP-complete

0 references

Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions

0 references

Q4198056

0 references

The Planar Hamiltonian Circuit Problem is NP-Complete

0 references

Advances on the Hamiltonian problem -- a survey

0 references

Hamiltonian properties of triangular grid graphs

0 references

Hamiltonian cycles in linear-convex supergrid graphs

0 references

Computing and Combinatorics

0 references

Hamilton Paths in Grid Graphs

0 references

Hamiltonian paths in some classes of grid graphs

0 references

A linear-time algorithm for the longest path problem in rectangular grid graphs

0 references

Hamiltonian paths in \(L\)-shaped grid graphs

0 references

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

0 references

Enumeration of Tours in Hamiltonian Rectangular Lattice Graphs

0 references

On Hamiltonian cycles and Hamiltonian paths

0 references

Understanding chicken walks on <i>n</i> × <i>n</i> grid: Hamiltonian paths, discrete dynamics, and rectifiable paths

0 references

Q4820877

0 references

Hamiltonian Properties of Grid Graphs

0 references

Approximating the longest paths in grid graphs

0 references

Identifiers

zbMATH Open document ID

1371.05287

0 references

DOI

10.1016/j.tcs.2017.05.031

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2399614

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2017.05.031
+Normal rank
@@ Property / OpenAlex ID @@
+W2623199383
@@ Property / OpenAlex ID: W2623199383 / rank @@
+Normal rank
@@ Property / cites work @@
+The Hamilton circuit problem on grids
@@ Property / cites work: The Hamilton circuit problem on grids / rank @@
+Normal rank
@@ Property / cites work @@
+An efficient algorithm for constructing Hamiltonian paths in meshes
+Normal rank
@@ Property / cites work @@
+The Hamiltonian circuit problem for circle graphs is NP-complete
+Normal rank
@@ Property / cites work @@
+Straight-Line Drawings on Restricted Integer Grids in Two and Three Dimensions
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+The Planar Hamiltonian Circuit Problem is NP-Complete
+Normal rank
@@ Property / cites work @@
+Advances on the Hamiltonian problem -- a survey
@@ Property / cites work: Advances on the Hamiltonian problem -- a survey / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian properties of triangular grid graphs
@@ Property / cites work: Hamiltonian properties of triangular grid graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian cycles in linear-convex supergrid graphs
+Normal rank
@@ Property / cites work @@
+Computing and Combinatorics
@@ Property / cites work: Computing and Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Hamilton Paths in Grid Graphs
@@ Property / cites work: Hamilton Paths in Grid Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian paths in some classes of grid graphs
@@ Property / cites work: Hamiltonian paths in some classes of grid graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for the longest path problem in rectangular grid graphs
+Normal rank
@@ Property / cites work @@
+Hamiltonian paths in \(L\)-shaped grid graphs
@@ Property / cites work: Hamiltonian paths in \(L\)-shaped grid graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A linear-time algorithm for finding Hamiltonian \((s,t)\)-paths in even-sized rectangular grid graphs with a rectangular hole
+Normal rank
@@ Property / cites work @@
+Enumeration of Tours in Hamiltonian Rectangular Lattice Graphs
+Normal rank
@@ Property / cites work @@
+On Hamiltonian cycles and Hamiltonian paths
@@ Property / cites work: On Hamiltonian cycles and Hamiltonian paths / rank @@
+Normal rank
@@ Property / cites work @@
+Understanding chicken walks on <i>n</i> × <i>n</i> grid: Hamiltonian paths, discrete dynamics, and rectifiable paths
+Normal rank
@@ Property / cites work @@
+Q4820877
@@ Property / cites work: Q4820877 / rank @@
+Normal rank
@@ Property / cites work @@
+Hamiltonian Properties of Grid Graphs
@@ Property / cites work: Hamiltonian Properties of Grid Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the longest paths in grid graphs
@@ Property / cites work: Approximating the longest paths in grid graphs / rank @@
+Normal rank