Graph algorithms analysis; Computational geometry; Mathematics of computing --> Graph algorithms -->

DOI:	10.2312/pg.20201228
Přístupová URL adresa:	https://explore.openaire.eu/search/publication?articleId=doi_________::c58b0de398a9428de04946f77fd049d5
Přírůstkové číslo:	edsair.doi...........c58b0de398a9428de04946f77fd049d5
Autor:	Reischl, Maximilian, Knauer, Christian, Guthe, Michael
Rok vydání:	2020
Předmět:	Graph algorithms analysis Graph algorithms Mathematics of computing Computational geometry Theory of computation
DOI:	10.2312/pg.20201228
Popis:	We present a new approach for path finding in weighted graphs using pre-computed minimal distance fields. By selecting the most promising minimal distance field at any given node and switching between them, our algorithm tries to find the shortest path. As we show, this approach scales very well for different topologies, hardware and graph sizes and has a mean length error below 1% while using reasonable amounts of memory. By keeping a simple structure and minimal backtracking, we are able to use the same approach on the massively parallel GPU, reducing the run time even further. Pacific Graphics Short Papers, Posters, and Work-in-Progress Papers Geometric Computations 37 42 Maximilian Reischl, Christian Knauer, and Michael Guthe CCS Concepts: Theory of computation --> Graph algorithms analysis; Computational geometry; Mathematics of computing --> Graph algorithms
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::c58b0de398a9428de04946f77fd049d5 Zobrazit plný text záznamu