Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Distance Oracles for Vertex-Labeled Graphs
verfasst von : Danny Hermelin, Avivit Levy, Oren Weimann, Raphael Yuster
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
Given a graph
G
= (
V
,
E
) with non-negative edge lengths whose vertices are assigned a
label
from
L
= {
λ
1
,…,
λ
ℓ
}, we construct a compact
distance oracle
that answers queries of the form: “What is
δ
(
v
,
λ
)?”, where
v
∈
V
is a vertex in the graph,
λ
∈
L
a vertex label, and
δ
(
v
,
λ
) is the distance (length of a shortest path) between
v
and the closest vertex labeled
λ
in
G
. We formalize this natural problem and provide a hierarchy of
approximate distance oracles
that require subquadratic space and return a distance of constant stretch. We also extend our solution to dynamic oracles that handle label changes in sublinear time.