On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems

Chung Lun Li, S. Thomas McCormick, David Simchi-Levi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

46 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)303-308
Number of pages6
JournalOperations Research Letters
Volume11
Issue number5
DOIs
Publication statusPublished - 1 Jan 1992
Externally publishedYes

Keywords

  • computational complexity
  • networks/ graphs
  • telecommunications
  • worst-case analysis

ASJC Scopus subject areas

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Cite this