Augmenting Graphs to Minimize the Diameter

Frati, F; Gaspers, S; Gudmundsson, J; Mathieson, L

Augmenting Graphs to Minimize the Diameter

Frati, F Gaspers, S Gudmundsson, J Mathieson, L

Permalink

Publication Type:: Journal Article
Citation:: Algorithmica, 2015, 72 (4), pp. 995 - 1010
Issue Date:: 2015-08-19

Closed Access

	Filename	Description	Size
	10.1007_978-3-642-45030-3_36.pdf	Published Version	308.89 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Frati, F	en_US
dc.contributor.author	Gaspers, S	en_US
dc.contributor.author	Gudmundsson, J	en_US
dc.contributor.author	Mathieson, L https://orcid.org/0000-0001-6470-2296	en_US
dc.date.issued	2015-08-19	en_US
dc.identifier.citation	Algorithmica, 2015, 72 (4), pp. 995 - 1010	en_US
dc.identifier.issn	0178-4617	en_US
dc.identifier.uri	http://hdl.handle.net/10453/123107
dc.description.abstract	© 2014, Springer Science+Business Media New York. 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$$4-approximation algorithm for the problem.	en_US
dc.relation.ispartof	Algorithmica	en_US
dc.relation.isbasedon	10.1007/s00453-014-9886-4	en_US
dc.subject.classification	Computation Theory & Mathematics	en_US
dc.title	Augmenting Graphs to Minimize the Diameter	en_US
dc.type	Journal Article
utslib.citation.volume	4	en_US
utslib.citation.volume	72	en_US
utslib.for	0802 Computation Theory and Mathematics	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access
pubs.issue	4	en_US
pubs.publication-status	Published	en_US
pubs.volume	72	en_US

Abstract:

© 2014, Springer Science+Business Media New York. 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$$4-approximation algorithm for the problem.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/123107