Complexity Results for Compressing Optimal Paths


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



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.




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



AAAI Technical Track: Heuristic Search and Optimization