Augmenting Graphs to Minimize the Diameter

作者：Frati Fabrizio; Gaspers Serge; Gudmundsson Joachim^*; Mathieson Luke

来源：Algorithmica, 2015, 72(4): 995-1010.

DOI：10.1007/s00453-014-9886-4

• Graph Algorithms
• Approximation algorithms
• Parametrized complexity

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 -approximation algorithm for the problem.

• 出版日期2015-8