License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2012.71
URN: urn:nbn:de:0030-drops-37048
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3704/
Go to the corresponding OASIcs Volume Portal

Bauer, Reinhard ; Baum, Moritz ; Rutter, Ignaz ; Wagner, Dorothea

On the Complexity of Partitioning Graphs for Arc-Flags

pdf-format:
9.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bauer_et_al:OASIcs:2012:3704,
  author =	{Reinhard Bauer and Moritz Baum and Ignaz Rutter and Dorothea Wagner},
  title =	{{On the Complexity of Partitioning Graphs for Arc-Flags}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{71--82},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Daniel Delling and Leo Liberti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3704},
  URN =		{urn:nbn:de:0030-drops-37048},
  doi =		{10.4230/OASIcs.ATMOS.2012.71},
  annote =	{Keywords: shortest paths, arc-flags, search space, preprocessing, complexity}
}

Keywords: shortest paths, arc-flags, search space, preprocessing, complexity
Collection: 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2012
Date of publication: 13.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI