{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:03Z","timestamp":1742617143590,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540558088"},{"type":"electronic","value":"9783540472919"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55808-x_15","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T09:44:54Z","timestamp":1330249494000},"page":"172-180","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of incremental computation"],"prefix":"10.1007","author":[{"given":"Suresh","family":"Chari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Desh","family":"Ranjan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pankaj","family":"Rohatgi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,30]]},"reference":[{"key":"15_CR1","unstructured":"A. Blum. Algorithms for Approximate Graph Coloring. PhD thesis, M.I.T., 1991."},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy. Approximating Clique is Almost NP-Complete. In 32nd Symposium on Foundation of Computer Science, pages 2\u201312, 1991.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"15_CR3","volume-title":"Computers and Intractability","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D. Johnson. Computers and Intractability. Freeman, San Fransisco, 1979."},{"key":"15_CR4","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D. Johnson","year":"1988","unstructured":"D. Johnson, C. Papadimitriou, and M. Yannakakis. How easy is local search. Journal of Computer and System Sciences, 37:179\u2013200, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR5","unstructured":"J. Kraj\u00ed\u010dek, P. Pudlk, and J. Sgall. Interactive Computation of Optimal Solutions. In Mathematical Foundations of Computer Science, Springer-Verlag LNCS #452, 1990."},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin. Computer solutions of the traveling salesman problem. Bell System Tech. J., 44:2245\u20132269, 1965.","journal-title":"Bell System Tech. J."},{"key":"15_CR7","first-page":"972","volume":"11","author":"S. Lin","year":"1973","unstructured":"S. Lin and B.W. Kernighan. An effective heuristic algorithm for the travelling salesman problem. Oper. Res., 11:972\u2013989, 1973.","journal-title":"Oper. Res."},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"A. Panconesi and D. Ranjan. Quantifiers and approximation. In 22nd ACM Symposium on Theory of Computing, pages 446\u2013456. ACM, 1990.","DOI":"10.1145\/100216.100275"},{"key":"15_CR9","volume-title":"Combinatorial Algorithms: Algorithms and Complexity","author":"C. Papadimitriou","year":"1982","unstructured":"C. Papadimitriou and K. Steiglitz. Combinatorial Algorithms: Algorithms and Complexity. Prentice-Hall, Englewodd Cliffs, NJ, 1982."},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"D. Ranjan, S. Chari, and P. Rohtagi. Improving known solutions is hard. In Proceedings of the 18 th ICALP, pages 381\u2013392. Springer-Verlag, 1991. Lecture Notes in Computer Science # 510.","DOI":"10.1007\/3-540-54233-7_149"},{"issue":"l","key":"15_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant and V.V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47(l):85\u201393, 1986.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1992"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55808-X_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:29:22Z","timestamp":1742592562000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55808-X_15"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540558088","9783540472919"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-55808-x_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"30 July 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}