THE COMPLEXITY OF THE NETWORK DESIGN PROBLEM

D. S. Johnson, J. K. Lenstra and A. H. G. Rinnooy Kan

No 272157, Econometric Institute Archives from Erasmus University Rotterdam

Abstract: In the network design problem we are given a weighted undirected graph. We wish to find a subgraph which connects all the original vertices and minimizes the sum of the shortest path weights between all vertex pairs, subject to a budget constraint on the sum of its edge weights. In this note we establish NP-completeness for the network design problem, even for the simple case where all edge weights are equal and the budget restricts the choice to spanning trees. This result justifies the development of enumerative optimization methods and of approximation algorithms, such as those described in a recent paper by R. Dionne and M. Florian.

Keywords: Agricultural and Food Policy; Research Methods/Statistical Methods (search for similar items in EconPapers)
Pages: 11
Date: 1977
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://ageconsearch.umn.edu/record/272157/files/erasmus094.pdf (application/pdf)
https://ageconsearch.umn.edu/record/272157/files/erasmus094.pdf?subformat=pdfa (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ags:eureia:272157

DOI: 10.22004/ag.econ.272157

Access Statistics for this paper

More papers in Econometric Institute Archives from Erasmus University Rotterdam Contact information at EDIRC.
Bibliographic data for series maintained by AgEcon Search ().