2015 | OriginalPaper | Buchkapitel
Approximate Distance Oracle in O(n2) Time and O(n) Space for Chordal Graphs
verfasst von : Gaurav Singh, N. S. Narayanaswamy, G. Ramakrishna
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer International Publishing
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 preprocess a given unweighted chordal graph
G
on
n
vertices in
O
(
n
2
) time to build a data structure of
O
(
n
) size such that any subsequent distance query can be answered in constant time with a bounded constant factor error. In particular, for each pair of vertices
u
i
,
u
j
∈
V
(
G
), 1 ≤
i
,
j
≤
n
, we take constant time to output a distance value
d
ij
≤ 2
d
G
(
u
i
,
u
j
) + 8 using our data structure, where
d
G
is the distance between
u
i
and
u
j
in
G
. In contrast, for the closely related APSP problem on chordal graphs, the current best algorithm runs in
O
(
n
2.373
) time. Our improvement comes from a relationship that we discover between the graph distance and minimum hitting sets of cliques on certain paths in a clique tree associated with a chordal graph. We design an efficient data structure which additively approximates (error of +3) these minimum hitting sets of cliques for all the paths in the clique tree. This data structure is then integrated with an efficient data structure which answers LCA queries in rooted trees to yield our distance oracle for the given chordal graph.