Complexity Results for Compressing Optimal Paths
Abstract
In this work we give a first tractability analysis of Compressed Path Databases, space efficient oracles used to very quickly identify the first arc on a shortest path. We study the complexity of computing an optimal compressed path database for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulalion points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms which yield optimal compression results for trees.
Cite
Text
Botea et al. "Complexity Results for Compressing Optimal Paths." AAAI Conference on Artificial Intelligence, 2015. doi:10.1609/AAAI.V29I1.9368Markdown
[Botea et al. "Complexity Results for Compressing Optimal Paths." AAAI Conference on Artificial Intelligence, 2015.](https://mlanthology.org/aaai/2015/botea2015aaai-complexity/) doi:10.1609/AAAI.V29I1.9368BibTeX
@inproceedings{botea2015aaai-complexity,
title = {{Complexity Results for Compressing Optimal Paths}},
author = {Botea, Adi and Strasser, Ben and Harabor, Daniel},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2015},
pages = {1100-1106},
doi = {10.1609/AAAI.V29I1.9368},
url = {https://mlanthology.org/aaai/2015/botea2015aaai-complexity/}
}