Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
Journal of graph algorithms and applications,
Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications
, Tome 5 (2001) no. 5, pp. 39-57
Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website
In network communication systems, frequently messages are routed along a minimum diameter spanning tree (MDST) of the network, to minimize the maximum delay in delivering a message. When a transient edge failure occurs, it is important to choose a temporary replacement edge which minimizes the diameter of a new spanning tree. Such an optimal replacement is called a best swap. As a natural extension, the all-best-swaps (ABS) problem is the problem of finding a best swap for every edge of the MDST. Given a weighted graph $G=(V,E)$, where $|V|=n$ and $|E|=m$, we solve the ABS problem in $O(n\sqrt{m})$ time and $O(m)$ space, thus improving previous bounds for $m = o(n^2)$. We also show that the diameter of the tree resulting from a best swap is at most $5/2$ aslong as the diameter of a MDST recomputed from scratch.
@article{JGAA_2001_5_5_a3,
author = {Enrico Nardelli and Guido Proietti and Peter Widmayer},
title = {Finding {All} the {Best} {Swaps} of a {Minimum} {Diameter} {Spanning} {Tree} {Under} {Transient} {Edge} {Failures}},
journal = {Journal of graph algorithms and applications},
pages = {39--57},
year = {2001},
volume = {5},
number = {5},
doi = {10.7155/jgaa.00039},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00039/}
}
TY - JOUR AU - Enrico Nardelli AU - Guido Proietti AU - Peter Widmayer TI - Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures JO - Journal of graph algorithms and applications PY - 2001 SP - 39 EP - 57 VL - 5 IS - 5 UR - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00039/ DO - 10.7155/jgaa.00039 LA - en ID - JGAA_2001_5_5_a3 ER -
%0 Journal Article %A Enrico Nardelli %A Guido Proietti %A Peter Widmayer %T Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures %J Journal of graph algorithms and applications %D 2001 %P 39-57 %V 5 %N 5 %U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00039/ %R 10.7155/jgaa.00039 %G en %F JGAA_2001_5_5_a3
Enrico Nardelli; Guido Proietti; Peter Widmayer. Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures. Journal of graph algorithms and applications, Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications , Tome 5 (2001) no. 5, pp. 39-57. doi: 10.7155/jgaa.00039
Cité par Sources :