Augmenting Outerplanar Graphs to Meet Diameter Requirements

Ishii, T.

Given a graph G = (V;E) and an integer D��1, we consider the problem of augmenting G by a minimum set of new edges so that the diameter becomes at most D. It is known that no constant factor approximation algorithms to this problem with an arbitrary graph G can be obtained unless P = NP, while the problem with only a few graph classes such as forests is approximable within a constant factor. In this paper, we give the first constant factor approximation algorithm to the problem with an outerplanar graph G. We also show that if the target diameter D is even, then the case where G is a partial 2-tree is also approximable within a constant.

Cite as: Ishii, T. (2012). Augmenting Outerplanar Graphs to Meet Diameter Requirements. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 123-132

(from crpit.com) (local if available)