Augmenting graphs to minimize the diameter

Fabrizio Frati; Serge Gaspers; Joachim Gudmundsson; Luke Mathieson

doi:10.1007/978-3-642-45030-3_36

Augmenting graphs to minimize the diameter

Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

4 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
Title of host publication	Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings
Editors	Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam
Pages	383-393
Number of pages	11
Volume	8283 LNCS
DOIs	https://doi.org/10.1007/978-3-642-45030-3_36
Publication status	Published - 2013
Event	24th International Symposium on Algorithms and Computation, ISAAC 2013 - Hong Kong, China Duration: 16 Dec 2013 → 18 Dec 2013

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8283 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	24th International Symposium on Algorithms and Computation, ISAAC 2013
Country/Territory	China
City	Hong Kong
Period	16/12/13 → 18/12/13

Access to Document

10.1007/978-3-642-45030-3_36

Cite this

Frati, F., Gaspers, S., Gudmundsson, J., & Mathieson, L. (2013). Augmenting graphs to minimize the diameter. In L. Cai, S.-W. Cheng, & T.-W. Lam (Eds.), Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings (Vol. 8283 LNCS, pp. 383-393). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS). https://doi.org/10.1007/978-3-642-45030-3_36

Frati, Fabrizio ; Gaspers, Serge ; Gudmundsson, Joachim et al. / Augmenting graphs to minimize the diameter. Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. editor / Leizhen Cai ; Siu-Wing Cheng ; Tak-Wah Lam. Vol. 8283 LNCS 2013. pp. 383-393 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9c6dbbc674fa413380392338d5605685,

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

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

year = "2013",

doi = "10.1007/978-3-642-45030-3_36",

language = "English",

isbn = "9783642450297",

volume = "8283 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "383--393",

editor = "Leizhen Cai and Siu-Wing Cheng and Tak-Wah Lam",

booktitle = "Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings",

note = "24th International Symposium on Algorithms and Computation, ISAAC 2013 ; Conference date: 16-12-2013 Through 18-12-2013",

}

Frati, F, Gaspers, S, Gudmundsson, J & Mathieson, L 2013, Augmenting graphs to minimize the diameter. in L Cai, S-W Cheng & T-W Lam (eds), Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. vol. 8283 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8283 LNCS, pp. 383-393, 24th International Symposium on Algorithms and Computation, ISAAC 2013, Hong Kong, China, 16/12/13. https://doi.org/10.1007/978-3-642-45030-3_36

Augmenting graphs to minimize the diameter. / Frati, Fabrizio; Gaspers, Serge; Gudmundsson, Joachim et al.
Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. ed. / Leizhen Cai; Siu-Wing Cheng; Tak-Wah Lam. Vol. 8283 LNCS 2013. p. 383-393 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8283 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Augmenting graphs to minimize the diameter

AU - Frati, Fabrizio

AU - Gaspers, Serge

AU - Gudmundsson, Joachim

AU - Mathieson, Luke

PY - 2013

Y1 - 2013

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.

UR - http://www.scopus.com/inward/record.url?scp=84893406832&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-45030-3_36

DO - 10.1007/978-3-642-45030-3_36

M3 - Conference proceeding contribution

AN - SCOPUS:84893406832

SN - 9783642450297

VL - 8283 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 383

EP - 393

BT - Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings

A2 - Cai, Leizhen

A2 - Cheng, Siu-Wing

A2 - Lam, Tak-Wah

T2 - 24th International Symposium on Algorithms and Computation, ISAAC 2013

Y2 - 16 December 2013 through 18 December 2013

ER -

Frati F, Gaspers S, Gudmundsson J, Mathieson L. Augmenting graphs to minimize the diameter. In Cai L, Cheng SW, Lam TW, editors, Algorithms and Computation - 24th International Symposium, ISAAC 2013, Proceedings. Vol. 8283 LNCS. 2013. p. 383-393. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-45030-3_36

Augmenting graphs to minimize the diameter

Abstract

Publication series

Other

Access to Document

Other files and links

Fingerprint

Cite this