The complexity of the network design problem

Networks - Tập 8 Số 4 - Trang 279-285 - 1978
David S. Johnson1, Jan Karel Lenstra2, A. H. G. Rinnooy Kan3
1Bell Laboratories, Murray Hill, New Jersey
2Mathematisch Centrum, Amsterdam, The Netherlands
3Erasmus University, Rotterdam, The Netherlands

Tóm tắt

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

Từ khóa


Tài liệu tham khảo

10.1515/9781400874651

10.1002/net.3230090104

Garey M. R. R. L.GrahamandD. S.Johnson “Some NP‐Complete Geometric Problems ”Proc. 8th Annual ACM Symp.Theorey Comput. 1976 pp.10–22.

10.1145/322077.322090

10.1137/0203015

10.1016/0020-0190(76)90095-8

10.1007/978-1-4684-2001-2_9

10.1002/net.1975.5.1.45

10.1016/0041-1647(69)90152-X

Wong R. T., 1976, A Survey of Network Design Problems

Thông tin
Thông tin xuất bản

Networks

Tập 8 Số 4

279-285

Thông tin tác giả