Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Preprocessing Speed-Up Techniques Is Hard
verfasst von : Reinhard Bauer, Tobias Columbus, Bastian Katz, Marcus Krug, Dorothea Wagner
Erschienen in: Algorithms and Complexity
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
During the last years, preprocessing-based techniques have been developed to compute shortest paths between two given points in a road network. These
speed-up techniques
make the computation a matter of microseconds even on huge networks. While there is a vast amount of experimental work in the field, there is still large demand on theoretical foundations. The preprocessing phases of most speed-up techniques leave open some degree of freedom which, in practice, is filled in a heuristical fashion. Thus, for a given speed-up technique, the problem arises of how to fill the according degree of freedom optimally. Until now, the complexity status of these problems was unknown. In this work, we answer this question by showing NP-hardness for the recent techniques.