{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:37:11Z","timestamp":1759667831896},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2006,12,15]],"date-time":"2006-12-15T00:00:00Z","timestamp":1166140800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2007,3,12]]},"DOI":"10.1007\/s10107-006-0060-x","type":"journal-article","created":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T13:04:35Z","timestamp":1166101475000},"page":"175-193","source":"Crossref","is-referenced-by-count":4,"title":["On the graphical relaxation of the symmetric traveling salesman polytope"],"prefix":"10.1007","volume":"110","author":[{"given":"Marcus","family":"Oswald","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gerhard","family":"Reinelt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk Oliver","family":"Theis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,12,15]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-56628-8","volume-title":"Linear optimization and Extensions: Problems and Solutions","author":"D. Alevras","year":"2001","unstructured":"Alevras D. and Padberg M.W. (2001). Linear optimization and Extensions: Problems and Solutions. Springer, Berlin Heidelberg New York"},{"key":"60_CR2","doi-asserted-by":"crossref","unstructured":"Applegate, D., Bixby R., Chv\u00e1tal, V., Cook W.: On the solution of the Traveling Salesman Problem. In: Doc. Math. J. DMV (Extra Volume ICM), pp. 645\u2013656 (1998)","DOI":"10.4171\/dms\/1-3\/62"},{"key":"60_CR3","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-45586-8_7","volume-title":"Computational Combinatorial Optimization","author":"D. Applegate","year":"2001","unstructured":"Applegate D., Bixby R., Chv\u00e1tal V. and Cook W. (2001). TSP cuts which do not conform to the template paradigm. In: J\u00fcnger, M. and Naddef, D. (eds) Computational Combinatorial Optimization, pp 261\u2013303. Springer, Berlin Heidelberg New York"},{"issue":"1\u20132","key":"60_CR4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10107-003-0440-4","volume":"97","author":"D. Applegate","year":"2003","unstructured":"Applegate D., Bixby R., Chv\u00e1tal V. and Cook W. (2003). Implementing the Dantzig-Fulkerson\u2013Johnson algorithm for large Traveling Salesman Problems. Math. Program. Ser. B 97(1\u20132): 91\u2013153","journal-title":"Math. Program. Ser. B"},{"issue":"2","key":"60_CR5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1287\/moor.16.2.259","volume":"16","author":"S.C. Boyd","year":"1991","unstructured":"Boyd S.C. and Cunningham W.H. (1991). Small Travelling Salesman Polytopes. Math. Oper. Res 16(2): 259\u2013271","journal-title":"Math. Oper. Res"},{"key":"60_CR6","doi-asserted-by":"crossref","unstructured":"Carr, R.: Separating over classes of TSP inequalities defined by 0-node lifting in polynomial time. In: Cunningham, W.H., McCormick, S.T., Queyranne M, (eds.), Proc. IPCO V, pp. 460\u2013474, (1996)","DOI":"10.1007\/3-540-61310-2_34"},{"issue":"1","key":"60_CR7","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/moor.1030.0058","volume":"29","author":"R. Carr","year":"2004","unstructured":"Carr R. (2004). Separation algorithms for classes of STSP inequalities arising from a new STSP relaxation. Math. Oper. Res, 29(1): 80\u201391","journal-title":"Math. Oper. Res,"},{"key":"60_CR8","first-page":"497","volume":"10","author":"T. Christof","year":"1991","unstructured":"Christof T., J\u00fcnger M. and Reinelt G. (1991). A complete description of the Traveling Salesman Polytope on 8 nodes. OR Letters 10: 497\u2013500","journal-title":"OR Letters"},{"key":"60_CR9","unstructured":"Christof, T., L\u00f6bel, A.: PORTA \u2014 a polyhedron representation algorithm, (1998) http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/PORTA"},{"key":"60_CR10","unstructured":"Christof, T., Reinelt, G.: SmaPo \u2014 library of Small Polytopes. http:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/SMAPO\/tsp"},{"key":"60_CR11","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1142\/S0218195901000560","volume":"11","author":"T. Christof","year":"2001","unstructured":"Christof T. and Reinelt G. (2001). Decomposition and parallelization techniques for enumerating the facets of combinatorial polytopes. Int. J. Comput. Geom. Appl. 11: 423\u2013437","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"60_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01582008","volume":"33","author":"G. Cornu\u00e9jols","year":"1985","unstructured":"Cornu\u00e9jols G., Fonlupt J. and Naddef D. (1985). The traveling salesman problem on a graph and some related integer polyhedra. Math. Program. 33: 1\u201327","journal-title":"Math. Program."},{"key":"60_CR13","first-page":"393","volume":"2","author":"G. Dantzig","year":"1954","unstructured":"Dantzig G., Fulkerson R. and Johnson S. (1954). Solution of a large-scale traveling salesman problem. Oper. Res. 2: 393\u2013410","journal-title":"Oper. Res."},{"key":"60_CR14","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0377-2217(85)90151-1","volume":"21","author":"B. Fleischmann","year":"1985","unstructured":"Fleischmann B. (1985). A cutting plane procedure for the travelling salesman problem on road networks. Eur. J. Oper. Res. 21: 307\u2013317","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"60_CR15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/BF01585700","volume":"53","author":"J. Fonlupt","year":"1992","unstructured":"Fonlupt J. and Naddef D. (1992). The traveling salesman problem in graphs with some excluded minors. Math. Program. 53(2): 147\u2013172","journal-title":"Math. Program."},{"issue":"2","key":"60_CR16","first-page":"335","volume":"69","author":"MX. Goemans","year":"1995","unstructured":"Goemans MX. (1995). Worst-case comparison of valid inequalities for the TSP. Math. Program. 69(2): 335\u2013349","journal-title":"Math. Program."},{"issue":"2","key":"60_CR17","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF01580607","volume":"60","author":"MX. Goemans","year":"1993","unstructured":"Goemans MX. and Bertsimas DJ. (1993). Survivable networks, linear programming relaxations and the parsimonious property. Math. Program. 60(2): 145\u2013166","journal-title":"Math. Program."},{"key":"60_CR18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/BF01582116","volume":"16","author":"M. Gr\u00f6tschel","year":"1979","unstructured":"Gr\u00f6tschel M. and Padberg MW. (1979). On the symmetric travelling salesman problem I: inequalities. Math. Program. 16: 265\u2013280","journal-title":"Math. Program."},{"key":"60_CR19","first-page":"225","volume-title":"Handbooks in Operations Research, Management Science","author":"M. J\u00fcnger","year":"1995","unstructured":"J\u00fcnger M., Reinelt G. and Rinaldi G. (1995). The traveling salesman problem. In: Ball, M.O., Magnanti, T.L., Monma, C.L., and Nemhauser, G.L. (eds) Handbooks in Operations Research, Management Science, vol. 7, chap. 4, pp 225\u2013330. Elsevier, Amsterdam"},{"key":"60_CR20","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/978-94-011-7557-9_9","volume-title":"Combinatorial Programming: Methods and Applications","author":"J.F. Maurras","year":"1975","unstructured":"Maurras J.F. (1975). Some results on the convex hull of Hamiltonian cycles of symmetric complete graphs. In: Roy, B. (eds) Combinatorial Programming: Methods and Applications, pp 179\u2013190. Reidel, Dordrecht"},{"key":"60_CR21","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF01586945","volume":"51","author":"D. Naddef","year":"1991","unstructured":"Naddef D. and Rinaldi G. (1991). The Symmetric Traveling Salesman Polytope and its graphical relaxation: Composition of valid inequalities. Math. Program. 51: 359\u2013400","journal-title":"Math. Program."},{"key":"60_CR22","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/BF01581259","volume":"58","author":"D. Naddef","year":"1993","unstructured":"Naddef D. and Rinaldi G. (1993). The graphical relaxation: A new framework for the Symmetric Traveling Salesman Polytope. Math. Program. 58: 53\u201388","journal-title":"Math. Program."},{"issue":"1","key":"60_CR23","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF01581260","volume":"58","author":"M. Queyranne","year":"1993","unstructured":"Queyranne M. and Wang Y. (1993). Hamiltonian path and Symmetric Travelling Salesman polytopes. Math. Program. 58(1): 89\u2013110","journal-title":"Math. Program."},{"key":"60_CR24","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley New York (1986)"},{"key":"60_CR25","volume-title":"Polyhedra, algorithms for the general routing problem","author":"D.O. Theis","year":"2005","unstructured":"Theis D.O. (2005). Polyhedra, algorithms for the general routing problem. PhD Thesis, University of Heidelberg, Germany"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0060-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-006-0060-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-006-0060-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T23:48:18Z","timestamp":1683676098000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-006-0060-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,15]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,3,12]]}},"alternative-id":["60"],"URL":"https:\/\/doi.org\/10.1007\/s10107-006-0060-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12,15]]}}}