Fast First-Move Queries through Run-Length Encoding

doi:10.1609/socs.v5i1.18311

Fast First-Move Queries through Run-Length Encoding

2021-09-01

0

OA

AI

DOI：10.1609/socs.v5i1.18311

原文链接

原文求助

摘要

En 中文

We introduce a novel preprocessing-based algorithm to solve the problem of determining the first arc of a shortest path in sparse graphs. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix.

Fast First-Move Queries through Run-Length Encoding

摘要

期刊

机构

引用论文