Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
(1 + ε)-Distance Oracles for Vertex-Labeled Planar Graphs
verfasst von : Mingfei Li, Chu Chung Christopher Ma, Li Ning
Erschienen in: Theory and Applications of Models of Computation
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
We consider vertex-labeled graphs, where each vertex
v
is attached with a label from a set of labels. The vertex-to-label distance query desires the length of the shortest path from the given vertex to the set of vertices with the given label. We show how to construct an oracle for a vertex-labeled planar graph, such that
$O(\frac{1}{\epsilon}n\log n)$
storing space is needed, and any vertex-to-label query can be answered in
$O(\frac{1}{\epsilon}\log n\log \Delta)$
time with stretch 1 +
ε
. Here, Δ is the hop-diameter of the given graph. For the case that Δ =
O
(log
n
), we construct a distance oracle that achieves
$O(\frac{1}{\epsilon}\log n)$
query time, without changing space usage.