zbMATH — the first resource for mathematics

The complexity of the network design problem. (English) Zbl 0395.94048

94C15 Applications of graph theory to circuits and networks
68Q25 Analysis of algorithms and problem complexity
94C30 Applications of design theory to circuits and networks
Full Text: DOI
[1] and , Applied Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1962. · Zbl 0106.34901 · doi:10.1515/9781400874651
[2] Dionne, Networks 9 pp 1– (1979)
[3] and , ”Some NP-Complete Geometric Problems,” Proc. 8th Annual ACM Symp. Theorey Comput., 1976, pp. 10–22.
[4] Garey, J. Assoc. Comput. Mach. 25 pp 499– (1978) · Zbl 0379.68035 · doi:10.1145/322077.322090
[5] Hu, SIAM J. Comput. 3 pp 188– (1974)
[6] Hyafil, Information Processing Letters 5 pp 15– (1976)
[7] ”Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, and , eds., Plenum Press, New York, 1972, pp. 85–103. · doi:10.1007/978-1-4684-2001-2_9
[8] Karp, Networks 5 pp 45– (1975)
[9] Scott, Trans. Res. 3 pp 201– (1969)
[10] ”A Survey of Network Design Problems,” Working Paper OR 053–76, Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1976.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.