MISC

2011年12月1日

Memory-constrained algorithms for shortest path problems

Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
  • Tetsuo Asano
  • ,
  • Benjamin Doerr

We present an algorithm computing a shortest path between to vertices in a square grid graph with edge weights that uses memory less than linear in the num- ber of vertices (apart from that for storing in the in- put). For any ε > 0, our algorithm uses a work space of O(n(1/2)+ε) words and runs in O(nO(1/ε)) time.

リンク情報
URL
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84882943039&origin=inward
ID情報
  • SCOPUS ID : 84882943039

エクスポート
BibTeX RIS