Selected Papers from the 1998 Dagstuhl Seminar on Graph Algorithms and Applications Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures Vol. 5, no. 5, pp. 39-57, 2001. Regular paper. Abstract 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. Submitted: January 1999. Revised: February 2000. Revised: December 2000. Communicated by Takao Nishizeki, Roberto Tamassia, and Dorothea Wagner article (PDF) BibTeX