Geodesic
On the Complexity of Partitioning Graphs for Arc-Flags
Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 265-299.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.
DOI : 10.7155/jgaa.00294
Keywords: shortest paths, arc-flags, search space, preprocessing, complexity, approximation 
@article{JGAA_2013_17_3_a5,
     author = {Reinhard Bauer and Moritz Baum and Ignaz Rutter and Dorothea Wagner},
     title = {On the {Complexity} of {Partitioning} {Graphs} for {Arc-Flags}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {265--299},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2013},
     doi = {10.7155/jgaa.00294},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00294/}
}
TY  - JOUR
AU  - Reinhard Bauer
AU  - Moritz Baum
AU  - Ignaz Rutter
AU  - Dorothea Wagner
TI  - On the Complexity of Partitioning Graphs for Arc-Flags
JO  - Journal of Graph Algorithms and Applications
PY  - 2013
SP  - 265
EP  - 299
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00294/
DO  - 10.7155/jgaa.00294
LA  - en
ID  - JGAA_2013_17_3_a5
ER  - 
%0 Journal Article
%A Reinhard Bauer
%A Moritz Baum
%A Ignaz Rutter
%A Dorothea Wagner
%T On the Complexity of Partitioning Graphs for Arc-Flags
%J Journal of Graph Algorithms and Applications
%D 2013
%P 265-299
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00294/
%R 10.7155/jgaa.00294
%G en
%F JGAA_2013_17_3_a5
Reinhard Bauer; Moritz Baum; Ignaz Rutter; Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags. Journal of Graph Algorithms and Applications, Tome 17 (2013) no. 3, pp. 265-299. doi : 10.7155/jgaa.00294. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00294/

Cité par Sources :