**Reference**:- Erik D. Demaine and Morteza Zadimoghaddam, “Minimizing the Diameter of a Network using Shortcut Edges”, in
*Proceedings of the 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2010)*, Lecture Notes in Computer Science, volume 6139, Bergen, Norway, June 21–23, 2010, pages 420–431. **Abstract**:-
We study the problem of minimizing the diameter of a graph by adding
*k*shortcut edges, for speeding up communication in an existing network design. We develop constant-factor approximation algorithms for different variations of this problem. We also show how to improve the approximation ratios using resource augmentation to allow more than*k*shortcut edges. We observe a close relation between the single-source version of the problem, where we want to minimize the largest distance from a given source vertex, and the well-known*k-median*problem. First we show that our constant-factor approximation algorithms for the general case solve the single-source problem within a constant factor. Then, using a linear-programming formulation for the single-source version, we find a (1 + ε)-approximation using*O*(*k*log*n*) shortcut edges. To show the tightness of our result, we prove that any (3/2 − ε)-approximation for the single-source version must use Ω(*k*log*n*) shortcut edges assuming P ≠ NP. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- Copyright held by the authors.
**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PostScript (305k), gzipped PostScript (140k), and PDF (172k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated November 24, 2020 by Erik Demaine.