On the complexity of finding paths in a
β
Arthur W. Chou; Ker-I Ko
π
Article
π
2004
π
John Wiley and Sons
π
English
β 342 KB
π 2 views
## Abstract The computational complexity of finding a shortest path in a twoβdimensional domain is studied in the Turing machineβbased computational model and in the discrete complexity theory. This problem is studied with respect to two formulations of polynomialβtime computable twoβdimensional do