{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,10]],"date-time":"2026-01-10T20:23:49Z","timestamp":1768076629867,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1-3","license":[{"start":{"date-parts":[[1997,10,1]],"date-time":"1997-10-01T00:00:00Z","timestamp":875664000000},"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":[[1997,10]]},"DOI":"10.1007\/bf02614311","type":"journal-article","created":{"date-parts":[[2007,4,28]],"date-time":"2007-04-28T00:34:10Z","timestamp":1177720450000},"page":"55-69","source":"Crossref","is-referenced-by-count":8,"title":["Efficiently solvable special cases of hard combinatorial optimization problems"],"prefix":"10.1007","volume":"79","author":[{"given":"Rainer E.","family":"Burkard","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"BF02614311_CR1","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K.S. Booth","year":"1976","unstructured":"K.S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-tree algorithms,Journal of Computer and System Sciences 13 (1976) 335\u2013379.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02614311_CR2","unstructured":"V.Y. Burdyuk and V.N. Trofimov, Generalization of the results of Gilmore and Gomory on the solution of the traveling salesman problem,Izw. Akad. Nauk SSSR, Tech. Kibernet., issue 3 (1976) 16\u201322 (in Russian); English translation in:Engineering Cybernetics 14 (1976) 12\u201318."},{"key":"BF02614311_CR3","first-page":"387","volume-title":"Discrete Location Theory","author":"R.E. Burkard","year":"1989","unstructured":"R.E. Burkard, Locations with spatial interactions: The quadratic assignment problem, in: R.L. Francis and P.B. Mirchandani, eds.,Discrete Location Theory (Academic Press, New York, 1989) 387\u2013437."},{"key":"BF02614311_CR4","series-title":"3 Report","volume-title":"Easy and hard cases of the quadratic assignment problem: A survey","author":"R.E. Burkard","year":"1997","unstructured":"R.E. Burkard, E. \u00c7ela, V.M. Demidenko, N.N. Metelski and G. W\u00f6ginger, Easy and hard cases of the quadratic assignment problem: A survey, SFB3 Report 104, Institut f\u00fcr Mathematik, TU Graz, Austria, 1997."},{"key":"BF02614311_CR5","series-title":"SFB Report","volume-title":"The quadratic assignment problem with an anti-Monge matrix and a Toeplitz matrix: Easy and hard cases","author":"R.E. Burkard","year":"1994","unstructured":"R.E. Burkard, E. \u00c7ela, G. Rote and G. W\u00f6ginger, The quadratic assignment problem with an anti-Monge matrix and a Toeplitz matrix: Easy and hard cases, SFB Report 34, Institut f\u00fcr Mathematik, TU Graz, Austria, 1994; also:Mathematical Programming, to appear."},{"key":"BF02614311_CR6","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/BF02253612","volume":"54","author":"R.E. Burkard","year":"1995","unstructured":"R.E. Burkard and V.G. De\u012dneko, Polynomially solvable cases of the traveling salesman problem and a new exponential neighborhood,Computing 54 (1995) 191\u2013211.","journal-title":"Computing"},{"key":"BF02614311_CR7","series-title":"SFB Report","volume-title":"Well-solvable special cases of the travelling salesman problem: A survey","author":"R.E. Burkard","year":"1995","unstructured":"R.E. Burkard, V.G. De\u012dneko, R. van Dal, J.A.A. van der Veen and G.J. W\u00f6ginger, Well-solvable special cases of the travelling salesman problem: A survey, SFB Report 52, Institut f\u00fcr Mathematik, TU Graz, Austria, 1995."},{"key":"BF02614311_CR8","series-title":"SFB Report","volume-title":"The traveling salesman problem on permuted Monge matrices","author":"R.E. Burkard","year":"1995","unstructured":"R.E. Burkard, V.G. De\u012dneko and G.J. W\u00f6ginger, The traveling salesman problem on permuted Monge matrices, SFB Report 31, Institut f\u00fcr Mathematik, TU Graz, Austria, 1995."},{"key":"BF02614311_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/3-540-61310-2_36","volume-title":"Integer Programming and Combinatorial Optimization","author":"R.E. Burkard","year":"1996","unstructured":"R.E. Burkard, V.G. De\u012dneko and G.J. W\u00f6ginger, The traveling salesman and the PQ-tree, in: W.H. Cunningham, S.T. McCormick and M. Queyranne, eds.,Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1084 (Springer, Berlin, 1996) 490\u2013504."},{"key":"BF02614311_CR10","first-page":"313","volume":"12","author":"R.E. Burkard","year":"1996","unstructured":"R.E. Burkard and T. Dud\u00e1s, Steiner minimum trees for equidistant points on two sides of an angle,Acta Cybernetica 12 (1996) 313\u2013324.","journal-title":"Acta Cybernetica"},{"key":"BF02614311_CR11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0012-365X(95)00275-2","volume":"161","author":"R.E. Burkard","year":"1996","unstructured":"R.E. Burkard, T. Dud\u00e1s and T. Maier, Cut and patch Steiner trees for ladders,Discrete Mathematics 161 (1996) 53\u201361.","journal-title":"Discrete Mathematics"},{"key":"BF02614311_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0166-218X(95)00103-X","volume":"70","author":"R.E. Burkard","year":"1996","unstructured":"R.E. Burkard, B. Klinz and R. Rudolf, Perspectives of Monge properties in optimization,Discrete Applied Mathematics 70 (1996) 95\u2013161.","journal-title":"Discrete Applied Mathematics"},{"key":"BF02614311_CR13","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1080\/02331939108843720","volume":"22","author":"R.E. Burkard","year":"1991","unstructured":"R.E. Burkard and J.A.A. van der Veen, Universal conditions for algebraic traveling salesman problems to be efficiently solvable,Optimization 22 (1991) 787\u2013814.","journal-title":"Optimization"},{"key":"BF02614311_CR14","series-title":"Lecture Notes in Computer Science","first-page":"406","volume-title":"Proceedings of ESA IV","author":"G. Christopher","year":"1996","unstructured":"G. Christopher, M. Farach and M. Trick, The structure of circular decomposable metrics, in: J. Diaz and M. Serna, eds.,Proceedings of ESA IV, Lecture Notes in Computer Science, Vol. 1136 (Springer, Berlin, 1996) 406\u2013418."},{"key":"BF02614311_CR15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1080\/0025570X.1989.11977416","volume":"62","author":"F.R.K. Chung","year":"1989","unstructured":"F.R.K. Chung, M. Gardner and R.L. Graham, Steiner trees on a checkerboard,Mathematics Magazine 62 (1989) 83\u201396.","journal-title":"Mathematics Magazine"},{"key":"BF02614311_CR16","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0167-5060(08)70332-7","volume":"2","author":"F.R.K. Chung","year":"1978","unstructured":"F.R.K. Chung and R.L. Graham, Steiner trees for ladders,Annals of Discrete Mathematics 2 (1978) 173\u2013200.","journal-title":"Annals of Discrete Mathematics"},{"key":"BF02614311_CR17","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF02591867","volume":"26","author":"G. Cornu\u00e9jols","year":"1983","unstructured":"G. Cornu\u00e9jols, D. Naddef and W.R. Pulleyblank, Halin graphs and the traveling salesman problem,Mathematical Programming 26 (1983) 287\u2013294.","journal-title":"Mathematical Programming"},{"key":"BF02614311_CR18","unstructured":"V.G. De\u012dneko and V.L. Filonenko, On the reconstruction of specially structured matrices,Aktualnyje Problemy EVM i Programmirovanije, Dnepropetrovsk, DGU (1979) (in Russian)."},{"key":"BF02614311_CR19","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s002360050058","volume":"33","author":"V.G. De\u012dneko","year":"1996","unstructured":"V.G. De\u012dneko, R. Rudolf and G.J. W\u00f6ginger, On the recognition of permuted Supnick and incomplete Monge matrices,Acta Informatica 33 (1996) 559\u2013569.","journal-title":"Acta Informatica"},{"key":"BF02614311_CR20","first-page":"128","volume-title":"Proceedings of ESA III, Lecture Notes in Computer Science, Vol. 979","author":"V.G. De\u012dneko","year":"1995","unstructured":"V.G. De\u012dneko, R. Rudolf and G.J. W\u00f6ginger, Sometimes travelling is easy: the master tour problem, in: P. Spirakis, ed.,Proceedings of ESA III, Lecture Notes in Computer Science, Vol. 979 (Springer, Berlin, 1995) 128\u2013141."},{"key":"BF02614311_CR21","first-page":"29","volume":"1","author":"V.M. Demidenko","year":"1979","unstructured":"V.M. Demidenko, The traveling salesman problem with asymmetric matrices,Izv. Akad. Nauk. BSSR, Ser. Fiz.-mat. Nauk 1 (1979) 29\u201335 (in Russian).","journal-title":"Izv. Akad. Nauk. BSSR, Ser. Fiz.-mat. Nauk"},{"key":"BF02614311_CR22","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF02187871","volume":"2","author":"D.Z. Du","year":"1987","unstructured":"D.Z. Du, F.K. Hwang and J.F. Weng, Steiner minimal trees on regular polygons,Discrete and Computational Geometry 2 (1987) 65\u201387.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02614311_CR23","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0196-6774(90)90031-9","volume":"11","author":"D. Eppstein","year":"1990","unstructured":"D. Eppstein, Sequence comparison with mixed convex and concave costs,Journal of Algorithms 11 (1990) 85\u2013101.","journal-title":"Journal of Algorithms"},{"key":"BF02614311_CR24","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1057\/jors.1995.61","volume":"46","author":"J.V. Ferreira","year":"1995","unstructured":"J.V. Ferreira and R.C. Guimaraes, A traveling salesman problem for the sequencing of duties in bus crew rotas,Journal of the Operational Research Society 46 (1995) 415\u2013426.","journal-title":"Journal of the Operational Research Society"},{"key":"BF02614311_CR25","unstructured":"N.E. Gaikov, On the minimization of a linear form on cycles, Minsk, 1980, Manuscript presented byVesti Akad. Nauk BSSR, Ser. Fiz. mat. Nauk 4, 128, deposited in VINITI (AISTI), Moscow, No. 479-80 (in Russian)."},{"key":"BF02614311_CR26","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1287\/opre.12.5.655","volume":"12","author":"P.C. Gilmore","year":"1964","unstructured":"P.C. Gilmore and R.E. Gomory, Sequencing a one state-variable machine: A solvable case of the traveling salesman problem,Operations Research 12 (1964) 655\u2013679.","journal-title":"Operations Research"},{"key":"BF02614311_CR27","first-page":"87","volume-title":"The Traveling Salesman Problem","author":"P.C. Gilmore","year":"1985","unstructured":"P.C. Gilmore, E.L. Lawler and D.B. Shmoys, Well-solved special cases, in E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D.B. Shmoys, eds.,The Traveling Salesman Problem (Wiley, Chichester, UK, 1985) Chapter 4, 87\u2013143."},{"key":"BF02614311_CR28","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1214\/aos\/1176348536","volume":"20","author":"M. Hallin","year":"1992","unstructured":"M. Hallin, G. Melard and X. Milhaud, Permutational extreme values of autocorrelation coefficients and a Pitman test against serial dependence,Annals of Statistics 20 (1992) 523\u2013534.","journal-title":"Annals of Statistics"},{"key":"BF02614311_CR29","first-page":"317","volume-title":"Convexity, Proceedings of Symposia in Pure Mathematics","author":"A.J. Hoffman","year":"1963","unstructured":"A.J. Hoffman, On simple linear programming problems in:Convexity, Proceedings of Symposia in Pure Mathematics (AMS, Providence, RI, 1963) 317\u2013327."},{"key":"BF02614311_CR30","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02061658","volume":"33","author":"F.K. Hwang","year":"1991","unstructured":"F.K. Hwang, A primer of the Euclidean Steiner problem,Annals of Operation Research 33 (1991) 73\u201384.","journal-title":"Annals of Operation Research"},{"key":"BF02614311_CR31","volume-title":"The Steiner Tree Problem, Annals of Discrete Mathematics, Vol. 53","author":"F.K. Hwang","year":"1992","unstructured":"F.K. Hwang, D.S. Richards and P. Winter,The Steiner Tree Problem, Annals of Discrete Mathematics, Vol. 53 (North-Holland, Amsterdam, 1992)."},{"key":"BF02614311_CR32","doi-asserted-by":"crossref","first-page":"1000","DOI":"10.4153\/CJM-1975-104-6","volume":"27","author":"K. Kalmanson","year":"1975","unstructured":"K. Kalmanson, Edgeconvex circuits and the traveling salesman problem,Canadian Journal of Mathematics 27 (1975) 1000\u20131010.","journal-title":"Canadian Journal of Mathematics"},{"key":"BF02614311_CR33","unstructured":"G. Monge, M\u00e9moires sur la th\u00e9orie des d\u00e9blais et des remblais, in:Histoire de l\u2019Academie Royale des Science, Ann\u00e9e M. DCCLXXXI, avec les M\u00e9moires de Math\u00e9matique et de Physique, pour la m\u00eame Ann\u00e9e, Tir\u00e9s des Registres de cette Acad\u00e9mie, Paris (1978) 666\u2013704."},{"key":"BF02614311_CR34","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0020-0190(91)90118-2","volume":"40","author":"J.K. Park","year":"1991","unstructured":"J.K. Park, A special case of then-vertex traveling salesman problem that can be solved in O (n) time,Information Processing Letters 40 (1991) 247\u2013254.","journal-title":"Information Processing Letters"},{"key":"BF02614311_CR35","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1287\/opre.35.5.772","volume":"35","author":"R.D. Plante","year":"1987","unstructured":"R.D. Plante, T.J. Lowe and R. Chandrasekaran, The product traveling salesman problem: An application and solution heuristic,Operations Research 35 (1987) 772\u2013783.","journal-title":"Operations Research"},{"key":"BF02614311_CR36","first-page":"A161","volume":"30","author":"F. Rendl","year":"1986","unstructured":"F. Rendl, Quadratic assignment problems on series-parallel digraphs,Zeitschrift f\u00fcr Operations Research 30 (1986) A161-A173.","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"key":"BF02614311_CR37","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0166-218X(92)00189-S","volume":"52","author":"R. Rudolf","year":"1994","unstructured":"R. Rudolf, Recognition ofd-dimensional Monge arrays,Discrete Applied Mathematics 52 (1994) 71\u201382.","journal-title":"Discrete Applied Mathematics"},{"key":"BF02614311_CR38","first-page":"533","volume":"253","author":"V.I. Sarvanov","year":"1980","unstructured":"V.I. Sarvanov, On the complexity of minimizing a linear form on a set of cyclic permutations,Dokl. AN SSSR 253 (1980) 533\u2013535 (in Russian); English translation in:Soviet Math. Dokl. 22, 118\u2013120.","journal-title":"Dokl. AN SSSR"},{"key":"BF02614311_CR39","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0166-218X(87)90031-X","volume":"17","author":"P. Winter","year":"1987","unstructured":"P. Winter, Steiner problem in Halin networks,Discrete Applied Mathematics 17 (1987) 281\u2013294.","journal-title":"Discrete Applied Mathematics"},{"key":"BF02614311_CR40","unstructured":"Q.F. Yang, R.E. Burkard, E. \u00c7ela and G. W\u00f6ginger, Hamiltonian cycles in circulant digraphs with two stripes, SFB Report 20, Institut f\u00fcr Mathematik, TU Graz, Austria, 1995; also:Discrete Mathematics, to appear."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614311.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02614311\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02614311","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T04:49:23Z","timestamp":1558327763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02614311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,10]]},"references-count":40,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[1997,10]]}},"alternative-id":["BF02614311"],"URL":"https:\/\/doi.org\/10.1007\/bf02614311","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,10]]}}}