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 articulation 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.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference |
| Subtitle of host publication | 25-30 January 2015 Austin, Texas USA |
| Editors | Blai Bonet, Sven Koenig |
| Place of Publication | Palo Alto California USA |
| Publisher | Association for the Advancement of Artificial Intelligence (AAAI) |
| Pages | 1100-1106 |
| Number of pages | 7 |
| Volume | 2 |
| ISBN (Print) | 9781577357001 |
| Publication status | Published - 2015 |
| Externally published | Yes |
| Event | AAAI Conference on Artificial Intelligence 2015 - Hyatt Regency, Austin, United States of America Duration: 25 Jan 2015 → 30 Jan 2015 Conference number: 29th http://www.aaai.org/Conferences/AAAI/aaai15.php |
Conference
| Conference | AAAI Conference on Artificial Intelligence 2015 |
|---|---|
| Abbreviated title | AAAI 2015 |
| Country/Territory | United States of America |
| City | Austin |
| Period | 25/01/15 → 30/01/15 |
| Other | co-located with the 27th Innovative Applications of Artificial Intelligence Conference |
| Internet address |