On the complexity of finding paths in a two-dimensional domain I: Shortest paths

✍ Scribed by Arthur W. Chou; Ker-I Ko

• Publisher: John Wiley and Sons
• Year: 2004
• Tongue: English
• Weight: 342 KB
• Volume: 50
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200310120

✦ Synopsis

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 domains: (A) domains with polynomialtime computable boundaries, and (B) polynomial‐time recognizable domains with polynomial‐time computable distance functions. It is proved that the shortest path problem has the polynomial‐space upper bound for domains of both type (A) and type (B); and it has a polynomial‐space lower bound for the domains of type (B), and has a #P lower bound for the domains of type (A). (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)