2011 | OriginalPaper | Buchkapitel
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
verfasst von : Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer
Erschienen in: Automata, Languages and Programming
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
A (1 +
ε
)–approximate distance oracle for a graph is a data structure that supports approximate point-to-point shortest-path-distance queries. The most relevant measures for a distance-oracle construction are: space, query time, and preprocessing time.
There are strong distance-oracle constructions known for planar graphs (Thorup, JACM’04) and, subsequently, minor-excluded graphs (Abraham and Gavoille, PODC’06). However, these require
$\Omega(\epsilon^{-1} n \lg n)$
space for
n
–node graphs.
In this paper, for planar graphs, bounded-genus graphs, and minor-excluded graphs we give distance-oracle constructions that require only
O
(
n
) space. The big
O
hides only a fixed constant, independent of
ε
and independent of genus or size of an excluded minor. The preprocessing times for our distance oracle are also faster than those for the previously known constructions. For planar graphs, the preprocessing time is
$O(n \lg^2 n)$
. However, our constructions have slower query times. For planar graphs, the query time is
$O(\epsilon^{-2} \lg^2 n)$
.
For all our linear-space results, we can in fact ensure, for any
δ
> 0, that the space required is only 1 +
δ
times the space required just to represent the graph itself.