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-01-01
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.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.
