{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T01:57:02Z","timestamp":1768269422650,"version":"3.49.0"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1979,12,1]],"date-time":"1979-12-01T00:00:00Z","timestamp":312854400000},"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":[[1979,12]]},"DOI":"10.1007\/bf01582116","type":"journal-article","created":{"date-parts":[[2005,4,28]],"date-time":"2005-04-28T04:28:41Z","timestamp":1114662521000},"page":"265-280","source":"Crossref","is-referenced-by-count":158,"title":["On the symmetric travelling salesman problem I: Inequalities"],"prefix":"10.1007","volume":"16","author":[{"given":"Martin","family":"Gr\u00f6tschel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred W.","family":"Padberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"Graphs et hypergraphs","author":"C. Berge","year":"1970","unstructured":"C. Berge,Graphs et hypergraphs (Dunod, Paris, 1970)."},{"key":"CR2","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/BF01580109","volume":"5","author":"V. Chv\u00e1tal","year":"1973","unstructured":"V. Chv\u00e1tal, \u201cEdmonds polytopes and weakly Hamiltonian graphs\u201d,Mathematical Programming 5 (1973) 29\u201340.","journal-title":"Mathematical Programming"},{"key":"CR3","first-page":"393","volume":"2","author":"G.B. Dantzig","year":"1954","unstructured":"G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, \u201cSolution of a large-scale travelling salesman problem\u201d,Operations Research 2 (1954) 393\u2013410.","journal-title":"Operations Research"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69","author":"J. Edmonds","year":"1965","unstructured":"J. Edmonds, \u201cMaximum matching and a polyhedron with 0, 1 vertices\u201d,Journal of Research of the National Buruea of Standards Sect. B 69 (1965) 125\u2013130.","journal-title":"Journal of Research of the National Buruea of Standards Sect. B"},{"key":"CR5","first-page":"89","volume-title":"Combinatorial structure and their applications","author":"J. Edmonds","year":"1970","unstructured":"J. Edmonds and E.L. Johnson, \u201cMatching: A well-solved class of integer linear programs\u201d, in R.K. Guy, H. Hanani, N. Sauer and J. Schonheim, eds.,Combinatorial structure and their applications (Gordon and Breach, New York, 1970) pp. 89\u201392."},{"key":"CR6","volume-title":"Integer programming","author":"R. Garfinkel","year":"1972","unstructured":"R. Garfinkel and G.L. Nemhauser,Integer programming (Wiley, New York, 1972)."},{"key":"CR7","volume-title":"Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems","author":"R.E. Gomory","year":"1964","unstructured":"R.E. Gomory, \u201cThe travelling salesman problem\u201d, in:Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, IBM Data Processing Division (White Plains, NY, 1964)."},{"key":"CR8","volume-title":"Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme","author":"M. Gr\u00f6tschel","year":"1977","unstructured":"M. Gr\u00f6tschel, \u201cPolyedrische Charakterisierungen kombinatorischer Optimierungsprobleme\u201d, Dissertation, Universit\u00e4t Bonn, 1977 (Verlag A. Hain, Meisenheim, 1977)."},{"key":"CR9","unstructured":"M. Gr\u00f6tschel, \u201cFurther results on the facial structure of the travelling salesman polytope\u201d, IX International Symposium on Mathematical Programming (Budapest, August 1976)."},{"key":"CR10","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cLinear characterizations of travelling salesman problems\u201d, EURO-I, First European Congress on Operations Research (Brussels, January 1975)."},{"key":"CR11","first-page":"207","volume-title":"Proceedings in Operations Research, 4","author":"M. Gr\u00f6tschel","year":"1974","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cZur Oberfl\u00e4chenstruktur des Travelling Salesman Polytopen\u201d, in: H.J. Zimmermann, A. Schub, H. Sp\u00e4th and J. Stoer, eds.,Proceedings in Operations Research, 4 (Physica-Verlag, W\u00fcrzburg, 1974) pp. 207\u2013211."},{"key":"CR12","unstructured":"M. Gr\u00f6tschel and M.W. Padberg: \u201cOn the travelling salesman problem\u201d, Joint National Meeting of ORSA and TIMS (Las Vegas, November 1975)."},{"key":"CR13","first-page":"33","volume":"21","author":"M. Gr\u00f6tschel","year":"1977","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cLineare Charakterisierungen von Travelling Salesman Problemen\u201d,Zeitschrift f\u00fcr Operations Research 21 (1977) 33\u201364.","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/BF01580454","volume":"8","author":"M. Gr\u00f6tschel","year":"1975","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cPartial linear characterizations of the asymmetric travelling salesman polytope\u201d,Mathematical Programming 8 (1975) 378\u2013381.","journal-title":"Mathematical Programming"},{"key":"CR15","volume-title":"\u201cOn the symmetric travelling salesman problem\u201d, Report No. 7536-OR","author":"M. Gr\u00f6tschel","year":"1975","unstructured":"M. Gr\u00f6tschel and M.W. Padberg, \u201cOn the symmetric travelling salesman problem\u201d, Report No. 7536-OR, Inst. f\u00fcr \u00d6konometrie und Operations Research, Universit\u00e4t Bonn (Bonn, 1975)."},{"key":"CR16","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 travelling salesman problem II: Lifting theorems and facets\u201d,Mathematical Programming 16 (1979) 281\u2013302 (this issue).","journal-title":"Mathematical Programming"},{"key":"CR17","volume-title":"Graph theory","author":"F. Harary","year":"1972","unstructured":"F. Harary,Graph theory (Addison-Wesley, Reading, MA, 1972)."},{"key":"CR18","first-page":"551","volume":"59","author":"I. Heller","year":"1953","unstructured":"I. Heller, \u201cOn the problem of shortest paths between point\u201d, I and II (Abstract),Bulletin of the American Mathematical Society 59 (1953) 551\u2013552.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"CR19","doi-asserted-by":"crossref","unstructured":"I. Heller, \u201cNeighbor relations on the convex of cyclic permutations\u201d,Pacific Journal of Mathematics (1956) 467\u2013477.","DOI":"10.2140\/pjm.1956.6.467"},{"key":"CR20","volume-title":"A linear programming approach for the travelling salesman problem","author":"S. Hong","year":"1971","unstructured":"S. Hong, \u201cA linear programming approach for the travelling salesman problem\u201d, Ph.D. Thesis, The Johns Hopkins University (Baltimore, 1971)."},{"key":"CR21","first-page":"83","volume-title":"Complexity of computer computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems\u201d, in: R.E. Miller and J.W. Thatcher, eds.,Complexity of computer computations (Plenum Press, New York, 1972) pp. 83\u2013103."},{"key":"CR22","first-page":"557","volume":"61","author":"H.W. Kuhn","year":"1955","unstructured":"H.W. Kuhn, \u201cOn certain convex polyhedra\u201d (Abstract),Bulletin of the American Mathematical Society 61 (1955) 557\u2013558.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"CR23","volume-title":"Polytopes \u00e0 sommets dans [0, 1] n","author":"J.F. Maurras","year":"1976","unstructured":"J.F. Maurras, \u201cPolytopes \u00e0 sommets dans [0, 1] n \u201d, Th\u00e8se, University of Paris (Paris, 1976)."},{"key":"CR24","unstructured":"K. Menger, \u201cBotenproblem\u201d, in: K. Menger, ed.,Ergebnisse eines mathematischen Kolloquiums (Wien 1930), Heft 2 (Leipzig, 1932) pp. 11\u201312."},{"key":"CR25","unstructured":"E. Netto,Lehrbuch der Combinatorik (Chelsea Publishing Company, New York)."},{"key":"CR26","first-page":"559","volume":"61","author":"R.Z. Norman","year":"1955","unstructured":"R.Z. Norman, \u201cOn the convex polyhedra of the symmetric travelling salesman problem\u201d (Abstract),Bulletin of the American Mathematical Society 61 (1955) 559.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"CR27","volume-title":"\u201cOn the symmetric travelling salesman problem: A computational study\u201d, T.J. Watson Research Report","author":"M.W. Padberg","year":"1977","unstructured":"M.W. Padberg and S. Hong, \u201cOn the symmetric travelling salesman problem: A computational study\u201d, T.J. Watson Research Report, IBM Research (Yorktown Heights, 1977)."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BF01585502","volume":"7","author":"M.W. Padberg","year":"1974","unstructured":"M.W. Padberg and M.R. Rao, \u201cThe travelling salesman problem and a class of polyhedra of diameter two\u201d,Mathematical Programming 7 (1974) 32\u201345.","journal-title":"Mathematical Programming"},{"key":"CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-46216-0","volume-title":"Convexity and optimization in finite dimensions I","author":"J. Stoer","year":"1970","unstructured":"J. Stoer and Ch. Witzgall,Convexity and optimization in finite dimensions I (Springer, Berlin 1970)."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582116.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01582116\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01582116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T11:15:45Z","timestamp":1556882145000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01582116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,12]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1979,12]]}},"alternative-id":["BF01582116"],"URL":"https:\/\/doi.org\/10.1007\/bf01582116","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,12]]}}}