Given a graph G = (V, E), positive integer D < |V| and B,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 Addition Problem is to find a superset of edges E′ ⊇ E with |E′/E| ≤ B such that the diameter of G′ = (V, E′) is minimized. We prove that the MCBD case is NP-hard even when D = 2 and describe a polynomial heuristic for BCMD with a constant worst-case bound. We 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.
- computational complexity
- networks/ graphs
- worst-case analysis
ASJC Scopus subject areas
- Management Science and Operations Research
- Industrial and Manufacturing Engineering
- Applied Mathematics