{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:26:26Z","timestamp":1743150386452,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":44,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387747583"},{"type":"electronic","value":"9780387747590"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-74759-0_437","type":"book-chapter","created":{"date-parts":[[2008,8,25]],"date-time":"2008-08-25T11:11:28Z","timestamp":1219662688000},"page":"2539-2545","source":"Crossref","is-referenced-by-count":2,"title":["Network Design Problems"],"prefix":"10.1007","author":[{"given":"Dietmar","family":"Cieslik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"437_CR1_437","volume-title":"Network flows: Theory, algorithms and applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: Theory, algorithms and applications. Prentice-Hall, Englewood Cliffs"},{"key":"437_CR2_437","first-page":"37","volume":"3","author":"O. Bor\u016fvka","year":"1926","unstructured":"Bor\u016fvka O (1926) O jist\u00e9m probl\u00e9mu minim\u00e1lnim. Pr\u00e1ca Moravsk\u00e9 Prirodov\u011bdeck\u00e9 Spolne\u010dnosti 3:37\u201358","journal-title":"Pr\u00e1ca Moravsk\u00e9 Prirodov\u011bdeck\u00e9 Spolne\u010dnosti"},{"key":"437_CR3_437","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1137\/0205051","volume":"5","author":"D. Cheriton","year":"1976","unstructured":"Cheriton D, Tarjan RE (1976) Finding minimum spanning trees. SIAM J Comput 5:724\u2013742","journal-title":"SIAM J. Comput."},{"key":"437_CR4_437","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-6585-4","volume-title":"Steiner minimal trees","author":"D. Cieslik","year":"1998","unstructured":"Cieslik D (1998) Steiner minimal trees. Kluwer, Dordrecht"},{"key":"437_CR5_437","first-page":"59","volume-title":"DIMACS, 40","author":"D Cieslik","year":"1998","unstructured":"Cieslik D (1998) Using Hadwiger numbers in network design. In: DIMACS, 40. Am Math Soc, Providence, pp\u00a059\u201378"},{"key":"437_CR6_437","volume-title":"What is mathematics?","author":"R. Courant","year":"1941","unstructured":"Courant R, Robbins H (1941) What is mathematics? Oxford Univ. Press, Oxford"},{"key":"437_CR7_437","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A\u00a0note on two problems in connection with graphs. Numer Math 1:269\u2013271","journal-title":"Numer. Math."},{"key":"437_CR8_437","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus SE, Wagner RA (1972) The Steiner problem in graphs. Networks 1:195\u2013207","journal-title":"Networks"},{"key":"437_CR9_437","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01758755","volume":"7","author":"D.-Z Du","year":"1992","unstructured":"Du D-Z, Hwang FK (1992) A\u00a0proof of the Gilbert\u2013Pollak conjecture on the Steiner ratio. Algorithmica 7:121\u2013136","journal-title":"Algorithmica"},{"key":"437_CR10_437","unstructured":"Fermat P (1934) Abhandlungen \u00fcber Maxima und Minima. Oswalds Klassiker der exakten Wissenschaft, vol\u00a0238. H. Miller, reprint from original."},{"key":"437_CR11_437","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford LR Jr, Fulkerson DR (1956) Maximal flow through a\u00a0network. Canad J Math 8:399\u2013404","journal-title":"Canad. J. Math."},{"key":"437_CR12_437","volume-title":"Network flow theory","author":"L.R. Ford","year":"1962","unstructured":"Ford LR Jr, Fulkerson DR (1962) Network flow theory. Princeton Univ. Press, Princeton"},{"key":"437_CR13_437","volume-title":"Graph theory applications","author":"L.R. Foulds","year":"1994","unstructured":"Foulds LR (1994) Graph theory applications. Springer, Berlin"},{"key":"437_CR14_437","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey MR, Johnson DS (1977) The rectilinear Steiner tree problem is NP-complete. SIAM J Appl Math 32:826\u2013834","journal-title":"SIAM J. Appl. Math."},{"key":"437_CR15_437","volume-title":"Computers and intractibility","author":"M.R. Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractibility. Freeman, New York"},{"key":"437_CR16_437","first-page":"459","volume":"X","author":"C.F. Gauss","year":"1917","unstructured":"Gauss CF (1917) Briefwechsel Gauss\u2013Schuhmacher. In: Werke, vol. X. pp\u00a0459\u2013468","journal-title":"Werke"},{"key":"437_CR17_437","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1002\/net.3230120402","volume":"12","author":"B. Gavish","year":"1982","unstructured":"Gavish B (1982) Topological design of centralized computer networks - Formulations and algorithms. Networks 12:355\u2013377","journal-title":"Networks"},{"key":"437_CR18_437","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"Gilbert EN, Pollak HO (1968) Steiner minimal trees. SIAM J Appl Math 16:1\u201329","journal-title":"SIAM J. Appl. Math."},{"key":"437_CR19_437","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1109\/MAHC.1985.10011","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"Graham RL, Hell P (1985) On the history of the minimum spanning tree problem. Ann Hist Comput 7:43\u201357","journal-title":"Ann. Hist. Comput."},{"key":"437_CR20_437","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1137\/0403043","volume":"3","author":"M. Gr\u00f6tschel","year":"1990","unstructured":"Gr\u00f6tschel M, Monma CL (1990) Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J Discret Math 3:502\u2013523","journal-title":"SIAM J. Discret Math."},{"key":"437_CR21_437","volume-title":"Handbook Oper. Res. and Management Sci.","author":"M. Gr\u00f6tschel","year":"1994","unstructured":"Gr\u00f6tschel M, Monma CL, Stoer M (1994) Design of survivable networks. In: Handbook Oper Res and Management Sci. North-Holland, Amsterdam"},{"key":"437_CR22_437","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1002\/net.3230010203","volume":"1","author":"S.B. Hakimi","year":"1971","unstructured":"Hakimi SB (1971) Steiner's problem in graphs and its implications. Networks 1:113\u2013133","journal-title":"Networks"},{"key":"437_CR23_437","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1090\/qam\/184873","volume":"22","author":"S.L. Hakimi","year":"1964","unstructured":"Hakimi SL, Yau SS (1964) Distance matrix of a\u00a0graph and its realizability. Quart Appl Math 22:305\u2013317","journal-title":"Quart. Appl. Math."},{"key":"437_CR24_437","volume-title":"Introduction to global optimization","author":"R. Horst","year":"1995","unstructured":"Horst R, Pardalos PM, Thoai NV (1995) Introduction to global optimization. Kluwer, Dordrecht"},{"key":"437_CR25_437","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F.K. Hwang","year":"1976","unstructured":"Hwang FK (1976) On Steiner minimal trees with rectilinear distance. SIAM J Appl Math 30:104\u2013114","journal-title":"SIAM J. Appl. Math."},{"key":"437_CR26_437","volume-title":"The Steiner tree problem","author":"F.K. Hwang","year":"1992","unstructured":"Hwang FK, Richards DS, Winter P (1992) The Steiner tree problem. North-Holland, Amsterdam"},{"key":"437_CR27_437","volume-title":"Minimal networks - The Steiner problem and its generalizations","author":"A.O. Ivanov","year":"1994","unstructured":"Ivanov AO, Tuzhilin AA (1994) Minimal networks - The Steiner problem and its generalizations. CRC Press, Boca Raton"},{"key":"437_CR28_437","volume-title":"Graphen, Netzwerke und Algorithmen","author":"D. Jungnickel","year":"1994","unstructured":"Jungnickel D (1994) Graphen, Netzwerke und Algorithmen. BI Wissenschaftsverlag, Mannheim"},{"key":"437_CR29_437","first-page":"85","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1962","unstructured":"Karp RM (1962) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of Computer\n\t  Computations. Springer, New York, pp\u00a085\u2013103"},{"key":"437_CR30_437","first-page":"48","volume":"7","author":"J.B. Kruskal","year":"1956","unstructured":"Kruskal JB (1956) On the shortest spanning subtree of a\u00a0graph and the travelling salesman problem. Proc 7:48\u201350","journal-title":"Proc.\u00a0"},{"key":"437_CR31_437","volume-title":"Combinatorial optimization - Networks and matroids","author":"E.L. Lawler","year":"1976","unstructured":"Lawler EL (1976) Combinatorial optimization - Networks and matroids. Holt, Rinehart and Winston, New York"},{"key":"437_CR32_437","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-322-92106-2","volume-title":"Combinatorial algorithms for integrated circuit layout","author":"T. Lengauer","year":"1990","unstructured":"Lengauer T (1990) Combinatorial algorithms for integrated circuit layout. Teubner and Wiley, Stuttgart"},{"key":"437_CR33_437","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1057\/jors.1972.6","volume":"23","author":"R.F. Love","year":"1972","unstructured":"Love RF, Morris JG (1972) Modelling inter-city road distances by mathematical function. J\u00a0Oper Res Soc 23:61\u201371","journal-title":"J. Oper. Res. Soc."},{"key":"437_CR34_437","volume-title":"Facilities location - Models and methods","author":"R.F. Love","year":"1989","unstructured":"Love RF, Morris JG, Wesolowsky G (1989) Facilities location - Models and methods. North-Holland, Amsterdam"},{"key":"437_CR35_437","doi-asserted-by":"crossref","first-page":"143","DOI":"10.4153\/CMB-1961-016-2","volume":"4","author":"Z.A. Melzak","year":"1961","unstructured":"Melzak ZA (1961) On the problem of Steiner. Canad Math Bull 4:143\u2013148","journal-title":"Canad. Math. Bull."},{"key":"437_CR36_437","volume-title":"Combinatorial optimization","author":"C.H. Papadimitriou","year":"1982","unstructured":"Papadimitriou CH, Steiglitz K (1982) Combinatorial optimization. Prentice-Hall, Englewood Cliffs"},{"key":"437_CR37_437","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02570700","volume":"14","author":"G. Robins","year":"1995","unstructured":"Robins G, Salowe JS (1995) Low-degree minimum spanning trees. Discrete Comput Geom 14:151\u2013165","journal-title":"Discrete Comput. Geom."},{"key":"437_CR38_437","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1009711003807","volume":"1","author":"J.H. Rubinstein","year":"1997","unstructured":"Rubinstein JH, Weng JF (1997) Compression theorems and Steiner ratios on spheres. J\u00a0Combin Optim 1:67\u201378","journal-title":"J. Combin. Optim."},{"key":"437_CR39_437","volume-title":"Introduction to computational molecular biology","author":"J. Setubal","year":"1997","unstructured":"Setubal J, Meidanis J (1997) Introduction to computational molecular biology. PWS, Boston, MA"},{"key":"437_CR40_437","doi-asserted-by":"crossref","unstructured":"Smith JM (1985) Generalized Steiner network problems in engineering design. In: Design Optimization. pp\u00a0119\u2013161","DOI":"10.1016\/B978-0-12-280910-1.50010-6"},{"key":"437_CR41_437","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"J.A. Wald","year":"1983","unstructured":"Wald JA, Colbourn CJ (1983) Steiner trees, partial 2-trees, and minimum IFI networks. Networks 13:159\u2013167","journal-title":"Networks"},{"key":"437_CR42_437","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230150305","volume":"15","author":"P. Winter","year":"1985","unstructured":"Winter P (1985) An algorithm for the Steiner problem in the Euclidean plane. Networks 15:323\u2013345","journal-title":"Networks"},{"key":"437_CR43_437","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0196-6774(86)90018-0","volume":"7","author":"P. Winter","year":"1986","unstructured":"Winter P (1986) Generalized Steiner problem in series-parallel networks. J\u00a0Algorithms 7:549\u2013566","journal-title":"J. Algorithms"},{"key":"437_CR44_437","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1002\/net.3230170203","volume":"17","author":"P. Winter","year":"1987","unstructured":"Winter P (1987) Steiner problems in networks: A\u00a0survey. Networks 17:129\u2013167","journal-title":"Networks"}],"container-title":["Encyclopedia of Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-74759-0_437","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T09:55:26Z","timestamp":1720691726000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-74759-0_437"}},"subtitle":["NDP"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387747583","9780387747590"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-74759-0_437","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}