{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T11:44:36Z","timestamp":1772192676195,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1990,1,1]],"date-time":"1990-01-01T00:00:00Z","timestamp":631152000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Programming"],"published-print":{"date-parts":[[1990,1]]},"DOI":"10.1007\/bf01585735","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T05:12:20Z","timestamp":1114665140000},"page":"153-171","source":"Crossref","is-referenced-by-count":116,"title":["Minimum-weight two-connected spanning networks"],"prefix":"10.1007","volume":"46","author":[{"given":"Clyde L.","family":"Monma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Beth Spellman","family":"Munson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"William R.","family":"Pulleyblank","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","unstructured":"Bell Laboratories, \u201cThe traveling salesman problem: 1934\u20131978,\u201d Bibliography No. 367 (Holmdel, NY, 1979)."},{"key":"CR2","volume-title":"Graphs and Hypergraphs","author":"C. Berge","year":"1973","unstructured":"C. Berge,Graphs and Hypergraphs (North-Holland, Amsterdam, 1973)."},{"key":"CR3","unstructured":"D. Bienstock, E.F. Brickell and C.L. Monma, \u201cProperties ofk-connected networks,\u201dSIAM Journal on Discrete Mathematics, to appear."},{"key":"CR4","volume-title":"\u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical Report","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cWorst-case analysis of a new heuristic for the traveling salesman problem,\u201d Technical Report, GSIA, Carnegie-Mellon University (Pittsburgh, PA, 1976)."},{"key":"CR5","first-page":"131","volume-title":"Combinatorial Optimization","author":"N. Christofides","year":"1979","unstructured":"N. Christofides, \u201cThe traveling salesman problem,\u201d in: N. Christofides et al., eds.,Combinatorial Optimization (Wiley, New York, 1979) pp. 131\u2013150."},{"key":"CR6","first-page":"705","volume-title":"Operational Research '81","author":"N. Christofides","year":"1981","unstructured":"N. Christofides and C.A. Whitlock, \u201cNetwork synthesis with connectivity constraints\u2014A survey,\u201d in: J.P. Brans, ed.,Operational Research '81 (North-Holland, Amsterdam, 1981) pp. 705\u2013723."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G. Cornu\u00e9jols","year":"1985","unstructured":"G. Cornu\u00e9jols, J. Fonlupt and D. Naddef, \u201cThe traveling salesman problem on a graph and some related integer polyhedra,\u201dMathematical Programming 33 (1985) 1\u201327.","journal-title":"Mathematical Programming"},{"key":"CR8","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01588956","volume":"14","author":"G. Cornu\u00e9jols","year":"1978","unstructured":"G. Cornu\u00e9jols and G.L. Nemhauser, \u201cTight bounds on Christofides' traveling salesman heuristic,\u201dMathematical Programming 14 (1978) 116\u2013121.","journal-title":"Mathematical Programming"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1287\/mnsc.26.5.495","volume":"26","author":"H. Crowder","year":"1980","unstructured":"H. Crowder and M.W. Padberg, \u201cSolving large-scale symmetric traveling salesman problems to optimality,\u201dManagement Science 26 (1980) 495\u2013509.","journal-title":"Management Science"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1287\/opre.7.1.58","volume":"7","author":"G.B. Dantzig","year":"1959","unstructured":"G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, \u201cOn a linear programming, combinatorial approach to the traveling salesman problem,\u201dOperations Research 7 (1959) 58\u201366.","journal-title":"Operations Research"},{"key":"CR11","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1971","unstructured":"S.E. Dreyfus and R.A. Wagner, \u201cThe Steiner problem in graphs,\u201dNetworks 1 (1971) 195\u2013207.","journal-title":"Networks"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"698","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cMaximum matching and a polytope with 0-1 vertices,\u201dJournal of Research of the National Bureau of Standards 698 (1965) 125\u2013130.","journal-title":"Journal of Research of the National Bureau of Standards"},{"key":"CR13","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1287\/moor.12.4.634","volume":"12","author":"R.E. Erickson","year":"1987","unstructured":"R.E. Erickson, C.L. Monma and A.F. Veinott Jr., \u201cSend-and-split method for minimum-concave-cost network flows,\u201dMathematics of Operations Research 12 (1987) 634\u2013664.","journal-title":"Mathematics of Operations Research"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"K.P. Eswaran","year":"1976","unstructured":"K.P. Eswaran and R.E. Tarjan, \u201cAugmentation problems,\u201dSIAM Journal on Computing 5 (1976) 653\u2013665.","journal-title":"SIAM Journal on Computing"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(82)90059-7","volume":"13","author":"G.N. Frederickson","year":"1982","unstructured":"G.N. Frederickson and J. Ja'Ja', \u201cOn the relationship between the biconnectivity augmentation and traveling salesman problem,\u201dTheoretical Computer Science 13 (1982) 189\u2013201.","journal-title":"Theoretical Computer Science"},{"key":"CR16","first-page":"93","volume":"32","author":"A.M. Frieze","year":"1979","unstructured":"A.M. Frieze, \u201cWorst-case analysis of algorithms for traveling salesman problems,\u201dOperational Research Verfahren 32 (1979) 93\u2013112.","journal-title":"Operational Research Verfahren"},{"key":"CR17","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A.M. Frieze","year":"1982","unstructured":"A.M. Frieze, G. Galbiati and F. Maffioli, \u201cOn the worst-case performance of some algorithms for the asymmetric traveling salesman problems,\u201dNetworks 12 (1982) 23\u201339.","journal-title":"Networks"},{"key":"CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979)."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"E.N. Gilbert and H.O. Pollak, \u201cSteiner minimal trees,\u201dSIAM Journal on Applied Mathematics 16 (1968) 1\u201329.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"CR20","first-page":"41","volume":"7","author":"R.L. Graham","year":"1985","unstructured":"R.L. Graham and P. Hell, \u201cOn the history of the minimum spanning tree problem,\u201dAnnals of the History of Computing 7 (1985) 41\u201357.","journal-title":"Annals of the History of Computing"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel and C.L. Monma, \u201cInteger polyhedra arising from certain network design problems with connectivity constraints,\u201dSIAM Journal on Discrete Mathematics, to appear.","DOI":"10.1137\/0403043"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cOn the symmetric traveling salesman problem I: Inequalities,\u201dMathematical Programming 16 (1979) 265\u2013280.","journal-title":"Mathematical Programming"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF01582117","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cOn the symmetric traveling salesman problem II: Lifting theorems and facets,\u201dMathematical Programming 16 (1979) 281\u2013302.","journal-title":"Mathematical Programming"},{"key":"CR24","volume-title":"The Traveling Salesman Problem","year":"1985","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem (Wiley, New York, 1985)."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF01902503","volume":"28","author":"L. Lov\u00e1sz","year":"1976","unstructured":"L. Lov\u00e1sz, \u201cOn some connectivity properties of Eulerian graphs,\u201dActa Mathematica Academiae Scientiarum Hungaricae 28 (1976) 129\u2013138.","journal-title":"Acta Mathematica Academiae Scientiarum Hungaricae"},{"key":"CR26","doi-asserted-by":"crossref","unstructured":"C.L. Monma and D.F. Shallcross, \u201cMethods for designing survivable communication networks,\u201dOperations Research (1989).","DOI":"10.1287\/opre.37.4.531"},{"key":"CR27","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1287\/moor.4.3.215","volume":"4","author":"C.L. Monma","year":"1979","unstructured":"C.L. Monma and J.B. Sidney, \u201cSequencing with series-parallel precedence constraints,\u201dMathematics of Operations Research 4 (1979) 215\u2013224.","journal-title":"Mathematics of Operations Research"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0012-365X(81)90006-6","volume":"34","author":"D. Naddef","year":"1981","unstructured":"D. Naddef and W.R. Pulleyblank, \u201cMatching in regular graphs,\u201dDiscrete Mathematics 34 (1981) 283\u2013291.","journal-title":"Discrete Mathematics"},{"key":"CR29","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"5","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and U.V. Vazirani, \u201cOn two geometric problems related to the traveling salesman problem,\u201dJournal of Algorithms 5 (1984) 231\u2013246.","journal-title":"Journal of Algorithms"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/nav.3800300107","volume":"30","author":"R.G. Parker","year":"1983","unstructured":"R.G. Parker and R.L. Rardin, \u201cThe traveling salesman problem: An update of research,\u201dNaval Research Logistics Quarterly 30 (1983) 69\u201396.","journal-title":"Naval Research Logistics Quarterly"},{"key":"CR31","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/net.3230180108","volume":"18","author":"J.S. Provan","year":"1988","unstructured":"J.S. Provan, \u201cConvexity and the Steiner tree problem,\u201dNetworks 18 (1988) 55\u201372.","journal-title":"Networks"},{"key":"CR32","volume-title":"\u201cOn minimizing setups in precedence constrained scheduling,\u201d Operations Research Technical Report 81185","author":"W.R. Pulleyblank","year":"1981","unstructured":"W.R. Pulleyblank, \u201cOn minimizing setups in precedence constrained scheduling,\u201d Operations Research Technical Report 81185, University of Bonn (Bonn, 1981)."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. J. Rosenkrantz","year":"1977","unstructured":"D. J. Rosenkrantz, R.E. Stearns and P.M. Lewis II, \u201cAn analysis of several heuristics for the traveling salesman problem,\u201dSIAM Journal on Computing 6 (1977) 563\u2013581.","journal-title":"SIAM Journal on Computing"},{"key":"CR34","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TCT.1969.1083004","volume":"16","author":"K. Steiglitz","year":"1969","unstructured":"K. Steiglitz, P. Weiner and D.J. Kleitman, \u201cThe design of minimum cost survivable networks,\u201dIEEE Transactions on Circuit Theory 16 (1969) 455\u2013460.","journal-title":"IEEE Transactions on Circuit Theory"},{"key":"CR35","doi-asserted-by":"crossref","first-page":"632","DOI":"10.1145\/322326.322328","volume":"29","author":"K. Takamizawa","year":"1982","unstructured":"K. Takamizawa, T. Nishizek and N. Saito, \u201cLinear-time computability of combinational problems on series parallel graphs,\u201dJournal ACM 29 (1982) 632\u2013641.","journal-title":"Journal ACM"},{"key":"CR36","first-page":"15","volume":"36","author":"J.A. Wald","year":"1982","unstructured":"J.A. Wald and C. Colbourn, \u201cSteiner trees in outerplanar graphs,\u201dCongressus Numeratum 36 (1982) 15\u201322.","journal-title":"Congressus Numeratum"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585735.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01585735\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01585735","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:32:31Z","timestamp":1556883151000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01585735"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,1]]},"references-count":36,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1990,1]]}},"alternative-id":["BF01585735"],"URL":"https:\/\/doi.org\/10.1007\/bf01585735","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,1]]}}}