Premium
The complexity of the network design problem
Author(s) -
Johnson D. S.,
Lenstra J. K.,
Kan A. H. G. Rinnooy
Publication year - 1978
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230080402
Subject(s) - combinatorics , shortest path problem , vertex (graph theory) , mathematics , network planning and design , undirected graph , simple (philosophy) , constraint (computer aided design) , mathematical optimization , graph , computer science , completeness (order theory) , enhanced data rates for gsm evolution , discrete mathematics , artificial intelligence , computer network , philosophy , geometry , epistemology , mathematical analysis
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.