Complexity Results for Compressing Optimal Paths

Authors

  • Adi Botea IBM Research, Dublin
  • Ben Strasser Karlsruhe Institute of Technology
  • Daniel Harabor NICTA

DOI:

https://doi.org/10.1609/aaai.v29i1.9368

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.

Downloads

Published

2015-02-16

How to Cite

Botea, A., Strasser, B., & Harabor, D. (2015). Complexity Results for Compressing Optimal Paths. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9368

Issue

Section

AAAI Technical Track: Heuristic Search and Optimization