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

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

doi:10.1016/0167-6377(92)90007-P

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 publication › Journal article › Academic research › peer-review

62 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 language	English
Pages (from-to)	303-308
Number of pages	6
Journal	Operations Research Letters
Volume	11
Issue number	5
DOIs	https://doi.org/10.1016/0167-6377(92)90007-P
Publication status	Published - 1 Jan 1992
Externally published	Yes

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

More information

10.1016/0167-6377(92)90007-P

Cite this

@article{421672249ea142ebac03196af7d1db51,

title = "On the minimum-cardinality-bounded-diameter and the bounded-cardinality-minimum-diameter edge addition problems",

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.",

keywords = "computational complexity, networks/ graphs, telecommunications, worst-case analysis",

author = "Li, {Chung Lun} and McCormick, {S. Thomas} and David Simchi-Levi",

year = "1992",

month = jan,

day = "1",

doi = "10.1016/0167-6377(92)90007-P",

language = "English",

volume = "11",

pages = "303--308",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

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

AU - Li, Chung Lun

AU - McCormick, S. Thomas

AU - Simchi-Levi, David

PY - 1992/1/1

Y1 - 1992/1/1

N2 - 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.

AB - 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.

KW - computational complexity

KW - networks/ graphs

KW - telecommunications

KW - worst-case analysis

UR - http://www.scopus.com/inward/record.url?scp=38249013164&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(92)90007-P

DO - 10.1016/0167-6377(92)90007-P

M3 - Journal article

SN - 0167-6377

VL - 11

SP - 303

EP - 308

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this