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.

Frati, F., Gaspers, S., Gudmundsson, J., & Mathieson, L. (2015). Augmenting Graphs to Minimize the Diameter. ALGORITHMICA, 72(4), 995-1010 [10.1007/s00453-014-9886-4].

Augmenting Graphs to Minimize the Diameter

FRATI, FABRIZIO;
2015

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.
Frati, F., Gaspers, S., Gudmundsson, J., & Mathieson, L. (2015). Augmenting Graphs to Minimize the Diameter. ALGORITHMICA, 72(4), 995-1010 [10.1007/s00453-014-9886-4].
File in questo prodotto:
File Dimensione Formato  
diameter-revisedv2.pdf

accesso aperto

Descrizione: Published version at https://doi.org/10.1007/s00453-014-9886-4
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 185.28 kB
Formato Adobe PDF
185.28 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/286685
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 22
  • ???jsp.display-item.citation.isi??? 16
social impact