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

DOI10.1002/malq.200310120zbMath1061.03039OpenAlexW2043907340MaRDI QIDQ3159412

Arthur W. Chou, Ker-I. Ko

Publication date: 16 February 2005

Published in: MLQ (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.200310120

zbMATH Keywords

computational complexityshortest pathpolynomial timecomputable analysispolynomial spaceoracle Turing machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain ⋮ On the complexity of computing the logarithm and square root functions on a complex domain ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Who Asked Us? How the Theory of Computing Answers Questions about Analysis ⋮ Jordan Areas and Grids ⋮ Complexity of Operators on Compact Sets ⋮ On the Complexity of Convex Hulls of Subsets of the Two-Dimensional Plane ⋮ Jordan Curves with Polynomial Inverse Moduli of Continuity ⋮ The computational complexity of distance functions of two-dimensional domains ⋮ Jordan curves with polynomial inverse moduli of continuity