Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Fast Deterministic Distributed Algorithms for Sparse Spanners
verfasst von : Bilel Derbel, Cyril Gavoille
Erschienen in: Structural Information and Communication Complexity
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
This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with
n
nodes. All previous deterministic distributed algorithms, for constant stretch spanner of
o
(
n
2
) edges, have a running time Ω(n
ε
) for some constant
ε
> 0 depending on the stretch. Our deterministic distributed algorithms construct constant stretch spanners of
o
(
n
2
) edges in
o
(
n
ε
) time for any constant
ε
> 0.
More precisely, in the Linial’s free model, we construct in
$n^{O(1/\sqrt{\log n})}$
time, for every graph, a 5-spanner of
O
(
n
3/2
) edges. The result is extended to
O
( k
2.322
)-spanners with
O
(
n
1 + 1/k
) edges for every parameter
k
≥1. If the minimum degree of the graph is
$\Omega(\sqrt{n})$
, then, in the same time complexity, a 9-spanner with
O
(
n
) edges can be constructed.