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. © 1992.
| Original language | English |
|---|---|
| Pages (from-to) | 303-308 |
| Journal | Operations Research Letters |
| Volume | 11 |
| Issue number | 5 |
| DOIs | |
| Publication status | Published - Jun 1992 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Research Keywords
- computational complexity
- networks/ graphs
- telecommunications
- worst-case analysis
Fingerprint
Dive into the research topics of 'On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver