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 Duration: 25 Jan 2015 → 30 Jan 2015 Conference number: 29th http://www.aaai.org/Conferences/AAAI/aaai14.php |
Conference
| Conference | AAAI Conference on Artificial Intelligence 2015 |
|---|---|
| Abbreviated title | AAAI 2015 |
| Country | United States |
| City | Austin |
| Period | 25/01/15 → 30/01/15 |
| Other | Co-located with the 27th Innovative Applications of Artificial Intelligence Conference. Papers at the AAAI 2015 conference will be related here. Any papers presented at the IAAI 2015 part of the conference will be related to that event. The two conferences should have a "relation" to each other put in place to recognise that the conferences were combined into one proceedings. |
| Internet address |
Cite this
}
Complexity results for compressing optimal paths. / Botea, Adi; Strasser, Ben; Harabor, Daniel.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference: 25-30 January 2015 Austin, Texas USA. ed. / Blai Bonet; Sven Koenig. Vol. 2 Palo Alto California USA : Association for the Advancement of Artificial Intelligence (AAAI), 2015. p. 1100-1106.Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review
TY - GEN
T1 - Complexity results for compressing optimal paths
AU - Botea, Adi
AU - Strasser, Ben
AU - Harabor, Daniel
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84959908827&partnerID=8YFLogxK
M3 - Conference Paper
SN - 9781577357001
VL - 2
SP - 1100
EP - 1106
BT - Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence and the Twenty-Seventh Innovative Applications of Artificial Intelligence Conference
A2 - Bonet, Blai
A2 - Koenig, Sven
PB - Association for the Advancement of Artificial Intelligence (AAAI)
CY - Palo Alto California USA
ER -