Augmenting Graphs to Minimize the Diameter

Fabrizio Frati; Serge Gaspers; Joachim Gudmundsson; Luke Mathieson

doi:10.1007/s00453-014-9886-4

Augmenting Graphs to Minimize the Diameter

Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson^*, Luke Mathieson

^*Corresponding author for this work

Faculty of Science and Engineering

Research output: Contribution to journal › Article › peer-review

36 Citations (Scopus)

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	https://doi.org/10.1007/s00453-014-9886-4
Publication status	Published - 19 Aug 2015

Keywords

Approximation algorithms
Graph Algorithms
Parametrized complexity

Access to Document

10.1007/s00453-014-9886-4

Cite this

@article{332e08b89fba4c219a66933e772b530d,

title = "Augmenting Graphs to Minimize the Diameter",

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.",

keywords = "Approximation algorithms, Graph Algorithms, Parametrized complexity",

author = "Fabrizio Frati and Serge Gaspers and Joachim Gudmundsson and Luke Mathieson",

year = "2015",

month = aug,

day = "19",

doi = "10.1007/s00453-014-9886-4",

language = "English",

volume = "72",

pages = "995--1010",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer, Springer Nature",

number = "4",

}

TY - JOUR

T1 - Augmenting Graphs to Minimize the Diameter

AU - Frati, Fabrizio

AU - Gaspers, Serge

AU - Gudmundsson, Joachim

AU - Mathieson, Luke

PY - 2015/8/19

Y1 - 2015/8/19

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

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

KW - Approximation algorithms

KW - Graph Algorithms

KW - Parametrized complexity

UR - https://www.scopus.com/pages/publications/84931563099

U2 - 10.1007/s00453-014-9886-4

DO - 10.1007/s00453-014-9886-4

M3 - Article

AN - SCOPUS:84931563099

SN - 0178-4617

VL - 72

SP - 995

EP - 1010

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

Augmenting Graphs to Minimize the Diameter

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this