We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n ^3 n) time, and (ii) the input graph is a tree, running in O(n^2 n) time. We also present an algorithm that computes a (1+ )-approximation in O(n + 1 ^3) time, for paths in R^d, where d is a constant.
The Diameter-Optimal @math -Augmentation Problem for edge-weighted graphs, and many of its variants, have been shown to be NP-hard @cite_16 , or even @math -hard @cite_6 @cite_18 . Because of this, several special classes of graphs have been considered. Chung and Gary @cite_13 and @cite_9 considered paths and cycles with unit edge weights and gave upper and lower bounds on the diameter that can be achieved. Ishii @cite_10 gave a constant factor approximation algorithm (approximating both @math and the diameter) for the case when the input graph is outerplanar. Erd o @cite_19 investigated upper and lower bounds for the case when the augmented graph must be triangle-free.
@cite_18 @cite_10 @cite_9 @cite_6 @cite_19 @cite_16 @cite_13
2148324291 2148734039 2021989224 2118748668 2014447809
The diameter of a graph is the maximum distance between any pair of vertices in the graph. The Diameter-tAugmentation problem takes as input a graph G=(V,E) and a positive integer k and asks whether there exists a set E"2 of at most k new edges so that the graph G"2=(V,[email protected]?E"2) has diameter t. This problem is NP-hard ( 1987) [10], even in the t=2 case ( 1992) [7]. We give a parameterized reduction from Dominating Set to Diameter-tAugmentation to prove that Diameter-tAugmentation is W[2]-hard for every t. Given an undirected graph and an integer , 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 , while the problem with only a few graph classes such as forests is approximable within a constant factor. In this article, 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. Let fd (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n0 (D) vertices, f2(G) = n - D - 1 and f3(G) ≥ n - O(D3). For d ≥ 4, fd (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of fd (G) over all connected graphs on n vertices is n-⌊d-2 ⌋ - O(1). As a byproduct, we show that for the n-cycle Cn, fd (Cn) = n-(2⌊d-2 ⌋ - 1) - O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000 1991 Mathematics Subject classification: 05C12. We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D − k for even D and of (k + 1)D − 2k + 2 for odd D ⩾ 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D − 1 and 4D − 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ⩽ 4 and k = 6, and k = 5 and k ⩾ 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ⩾ 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete. The main question addressed in this article is the following: If t edges are removed from a (t + 1) edge-connected graph G having diameter D, how large can the diameter of the resulting graph be? (The diameter of a graph is the maximum, over all pairs of vertices, of the length of the shortest path joining those vertices.) We provide bounds on this value that imply that the maximum possible diameter of the resulting graph, for large D and fixed t, is essentially (t + 1) · D. The bulk of the proof consists of showing that, if t edges are added to an n-vertex path Pn, then the diameter of the resulting graph is at least (n (t + 1)) - 1. Using a similar proof, we also show that if t edges are added to an n-vertex cycle Cn, then the least possible diameter of the resulting graph is (for large n) essentially n (t + 2) when t is even and n (t + 1) when t is odd. Examples are given in all these cases to show that there exist graphs for which the bounds are achieved. We also give results for the corresponding vertex deletion problem for general graphs. Such results are of interest, for example, when studying the potential effects of node or link failures on the performance of a communication network, especially for networks in which the maximum time-delay or signal degradation is directly related to the diameter of the network.