𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Euclidean shortest paths in the presence of rectilinear barriers

✍ Scribed by D. T. Lee; F. P. Preparata

Publisher
John Wiley and Sons
Year
1984
Tongue
English
Weight
990 KB
Volume
14
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

All-pairs shortest-paths computation in
All-pairs shortest-paths computation in the presence of negative cycles
✍ Kurt Mehlhorn; Volker Priebe; Guido SchΓ€fer; Naveen Sivadasan πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 49 KB

We present an algorithm that solves the all-pairs shortest-paths problem on a directed graph with n vertices and m arcs in time O(nm + n 2 log n), where the arcs are assigned real, possibly negative costs. Our algorithm is new in the following respect. It computes the distance Β΅(v, w) between each p

On the complexity of finding paths in a
On the complexity of finding paths in a two-dimensional domain I: Shortest paths
✍ 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