Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
verfasst von : Jun Luo, Christian Wulff-Nilsen
Erschienen in: Algorithms and 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
Given a graph embedded in a metric space, its dilation is the maximum over all distinct pairs of vertices of the ratio between their distance in the graph and the metric distance between them. Given such a graph
G
with
n
vertices and
m
edges and consisting of at most two connected components, we consider the problem of augmenting
G
with an edge such that the resulting graph has minimum dilation. We show that we can find such an edge in
$O((n^4\log n)/\sqrt m)$
time using linear space which solves an open problem of whether a linear-space algorithm with
o
(
n
4
) running time exists. We show that
O
(
n
2
log
n
) time is achievable if
G
is a simple path or the union of two vertex-disjoint simple paths. Finally, we show how to find an edge that maximizes the dilation of the resulting graph in
O
(
n
3
) time with
O
(
n
2
) space and in
O
(
n
3
log
n
) time with linear space.