{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T14:07:57Z","timestamp":1709388477285},"reference-count":10,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1987,3,1]],"date-time":"1987-03-01T00:00:00Z","timestamp":541555200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1987,3]]},"DOI":"10.1007\/bf02187869","type":"journal-article","created":{"date-parts":[[2005,10,29]],"date-time":"2005-10-29T04:51:54Z","timestamp":1130561514000},"page":"37-48","source":"Crossref","is-referenced-by-count":1,"title":["A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems"],"prefix":"10.1007","volume":"2","author":[{"given":"Martin","family":"Kolinek","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1987,3,1]]},"reference":[{"key":"BF02187869_CR1","first-page":"85","volume-title":"All shortest routes from a fixed origin in a graph,Theory of Graphs","author":"G. B. Dantzig","year":"1967","unstructured":"G. B. Dantzig, W. O. Blattner, and M. R. Rao, All shortest routes from a fixed origin in a graph,Theory of Graphs (Proc. Internat. Sympos., Rome, July 1966), 85\u201390, Gordon and Breach, New York, 1967."},{"key":"BF02187869_CR2","unstructured":"D. Dobkin and R. J. Lipton, On some generalizations of binary search, preprint."},{"key":"BF02187869_CR3","volume-title":"Computers and Intractibility: A Guide to the Theory of NP-completness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson,Computers and Intractibility: A Guide to the Theory of NP-completness, Freeman, San Francisco, 1979."},{"key":"BF02187869_CR4","volume-title":"Convex Polytopes","author":"B. Gr\u00fcnbaum","year":"1967","unstructured":"B. Gr\u00fcnbaum,Convex Polytopes, Interscience, New York, 1967."},{"key":"BF02187869_CR5","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1145\/828.322450","volume":"31","author":"F. Meyer auf der Heide","year":"1984","unstructured":"F. Meyer auf der Heide, A polynomial linear search algorithm for then-dimensional knapsack problem,J. Assoc. Comput. Mach. 31 (1984), 668\u2013676.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02187869_CR6","doi-asserted-by":"crossref","unstructured":"F. Meyer auf der Heide, Fast algorithms for theN-dimensional restrictions of hard problems,Proceedings of the 17th STOC, 413\u2013420, 1985.","DOI":"10.1145\/22145.22191"},{"key":"BF02187869_CR7","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/S0022-0000(72)80034-5","volume":"6","author":"M. O. Rabin","year":"1972","unstructured":"M. O. Rabin, Proving simultaneous positivity of linear forms,J. Comput. System Sci. 6 (1972), 639\u2013650.","journal-title":"J. Comput. System Sci."},{"key":"BF02187869_CR8","unstructured":"O. Schreier and E. Sperner,Modern Algebra and Matrix Theory, translated by M. David and M. Hauser, Chelsea, New York, 1951."},{"key":"BF02187869_CR9","unstructured":"O. Schreier and E. Sperner,Projective Geometry in n Dimensions, translated by C. A. Rogers, Chelsea, New York, 1961."},{"key":"BF02187869_CR10","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1137\/0209028","volume":"9","author":"A. C. Yao","year":"1980","unstructured":"A. C. Yao and R. L. Rivest, On the polyhedral decision problem,SIAM J. Comput. 9 (1980), 343\u2013347.","journal-title":"SIAM J. Comput."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187869.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187869\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T13:22:36Z","timestamp":1557840156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187869"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,3]]},"references-count":10,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1987,3]]}},"alternative-id":["BF02187869"],"URL":"https:\/\/doi.org\/10.1007\/bf02187869","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,3]]}}}