Name
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 polynomial-time 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). (C) 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1002/malq.200310120 | MATHEMATICAL LOGIC QUARTERLY |
Keywords | Field | DocType |
shortest path,computational complexity,polynomial time,polynmial space | Discrete mathematics,Combinatorics,Shortest path problem,Upper and lower bounds,Turing machine,Time complexity,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
50 | 6 | 0942-5616 |
Citations | PageRank | References |
8 | 0.64 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arthur W. Chou | 1 | 41 | 6.26 |
| Ker-I Ko | 2 | 196 | 28.54 |