Abstract
We study the problem of augmenting a weighted graph by inserting edges of bounded total cost while minimizing the diameter of the augmented graph. Our main result is an FPT 4-approximation algorithm for the problem.
Original language | English |
---|---|
Pages (from-to) | 995-1010 |
Number of pages | 16 |
Journal | Algorithmica |
Volume | 72 |
Issue number | 4 |
DOIs | |
Publication status | Published - 19 Aug 2015 |
Keywords
- Approximation algorithms
- Graph Algorithms
- Parametrized complexity