Memory-constrained algorithms for shortest path problems

Tetsuo Asano; Benjamin Doerr

Memory-constrained algorithms for shortest path problems

Tetsuo Asano
, Benjamin Doerr

Japan Advanced Institute of Science and Technology
Max-Planck-Institut fur Informatik

Résultats de recherche: Contribution à une conférence › Papier › Revue par des pairs

22 Citations (Scopus)

Résumé

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.

langue originale	Anglais
état	Publié - 1 déc. 2011
Modification externe	Oui
Evénement	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 - Toronto, ON, Canada Durée: 10 août 2011 → 12 août 2011

Une conférence

Une conférence	23rd Annual Canadian Conference on Computational Geometry, CCCG 2011
Pays/Territoire	Canada
La ville	Toronto, ON
période	10/08/11 → 12/08/11

Contient cette citation

@conference{4c2995b7a948430d8eb684c6ca94ec18,

title = "Memory-constrained algorithms for shortest path problems",

abstract = "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.",

author = "Tetsuo Asano and Benjamin Doerr",

year = "2011",

month = dec,

day = "1",

language = "English",

note = "23rd Annual Canadian Conference on Computational Geometry, CCCG 2011 ; Conference date: 10-08-2011 Through 12-08-2011",

}

TY - CONF

T1 - Memory-constrained algorithms for shortest path problems

AU - Asano, Tetsuo

AU - Doerr, Benjamin

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

M3 - Paper

AN - SCOPUS:84882943039

T2 - 23rd Annual Canadian Conference on Computational Geometry, CCCG 2011

Y2 - 10 August 2011 through 12 August 2011

ER -

Memory-constrained algorithms for shortest path problems

Résumé

Une conférence

Empreinte digitale

Contient cette citation