Given a graph G=(V,E), positive integers D<ℝVℝ and B, the Minimum-Cardinality-Bounded-Diameter (MCBD) Edge Addition Problem is to find a superset of edges E'ℝE such that the graph G'=(V,E') has diameter no greater than D and the total number of the new edges is minimized, while the Bounded-Cardinality-Minimum-Diameter (BCMD) Edge Additional Problem is to find a superset of edges E'ℝE with ℝE'z.drule;Eℝ•B such that the diameter of G'=(V,E') is minimized. The authors prove that the MCBD case is NP-hard even when D=2 and describe a polynomial heuristic for BCMD with a constant worse-case bound. They also show that finding a polynomial heuristic for MCBD with a constant worst-case bound is no easier than finding such a heuristic for the dominating set problem.
