Geodesic
Small Stretch Spanners on Dynamic Graphs
Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 365-385.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

We present fully dynamic algorithms for maintaining 3- and 5-spanners of undirected graphs under a sequence of update operations. For unweighted graphs we maintain a 3-spanner or a 5-spanner under insertions and deletions of edges; on a graph with n vertices each operation is performed in O(∆) amortized time over a sequence of Ω(n) updates, where ∆ is the maximum degree of the original graph. The maintained 3-spanner (resp., 5-spanner) has O(n3/2) edges (resp., O(n4/3) edges), which is known to be optimal. On weighted graphs with d different edge cost values, we maintain a 3- or 5-spanner within the same amortized time bounds over a sequence of Ω(d ·n) updates. The maintained 3-spanner (resp., 5-spanner) has O(d ·n3/2) edges (resp., O(d ·n4/3) edges). The same approach can be extended to graphs with real-valued edge costs in the range [1,C]. All our algorithms are deterministic and are substantially faster than recomputing a spanner from scratch after each update.
DOI : 10.7155/jgaa.00133
Keywords: graph algorithms, dynamic algorithms, graph spanners 
@article{JGAA_2006_10_2_a13,
     author = {Giorgio Ausiello and Paolo Franciosa and Giuseppe Italiano},
     title = {Small {Stretch} {Spanners} on {Dynamic} {Graphs}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {365--385},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2006},
     doi = {10.7155/jgaa.00133},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00133/}
}
TY  - JOUR
AU  - Giorgio Ausiello
AU  - Paolo Franciosa
AU  - Giuseppe Italiano
TI  - Small Stretch Spanners on Dynamic Graphs
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 365
EP  - 385
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00133/
DO  - 10.7155/jgaa.00133
LA  - en
ID  - JGAA_2006_10_2_a13
ER  - 
%0 Journal Article
%A Giorgio Ausiello
%A Paolo Franciosa
%A Giuseppe Italiano
%T Small Stretch Spanners on Dynamic Graphs
%J Journal of Graph Algorithms and Applications
%D 2006
%P 365-385
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00133/
%R 10.7155/jgaa.00133
%G en
%F JGAA_2006_10_2_a13
Giorgio Ausiello; Paolo Franciosa; Giuseppe Italiano. Small Stretch Spanners on Dynamic Graphs. Journal of Graph Algorithms and Applications, Tome 10 (2006) no. 2, pp. 365-385. doi : 10.7155/jgaa.00133. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00133/

Cité par Sources :