{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:17Z","timestamp":1742598617575,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540587156"},{"type":"electronic","value":"9783540490548"}],"license":[{"start":{"date-parts":[[1994,1,1]],"date-time":"1994-01-01T00:00:00Z","timestamp":757382400000},"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":[[1994]]},"DOI":"10.1007\/3-540-58715-2_136","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:42:04Z","timestamp":1330274524000},"page":"342-353","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Approximation schemes using L-reductions"],"prefix":"10.1007","author":[{"suffix":"Jr","given":"H. B.","family":"Hunt","sequence":"first","affiliation":[]},{"given":"M. V.","family":"Marathe","sequence":"additional","affiliation":[]},{"given":"V.","family":"Radhakrishnan","sequence":"additional","affiliation":[]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"D. J.","family":"Rosenkrantz","sequence":"additional","affiliation":[]},{"given":"R. E.","family":"Stearns","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, Madhu Sudan and M. Szegedy, \u201cProof Verification and Hardness of Approximation Problems\u201d, Proc. 33rd IEEE FOCS, Oct. 1992, pp 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"B.S. Baker, \u201cApproximation Algorithms for NP-complete Problems on Planar Graphs,\u201d Proc. 24th IEEE FOCS, Nov. 1983, pp 265\u2013273. (Journal version: J. ACM, Vol. 41, No. 1, Jan. 1994, pp 153\u2013180.)","DOI":"10.1145\/174644.174650"},{"key":"28_CR3","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"R. Bar-Yehuda and S. Even, \u201cA Local Ratio Theorem for Approximating the Weighted Vertex Cover Problem,\u201d in Analysis and Design of Algorithms for Combinatorial Problems, Annals of Discrete Mathematics, Vol. 25, North Holland Publications, 1985, pp 27\u201345.","journal-title":"Analysis and Design of Algorithms for Combinatorial Problems, Annals of Discrete Mathematics"},{"key":"28_CR4","first-page":"1","volume":"344","author":"H.L. Bodlaender","year":"1988","unstructured":"H.L. Bodlaender, \u201cNC Algorithms for Graphs with Bounded Treewidth\u201d, Proc. WG'88, Springer-Verlag LNCS 344, 1988, pp 1\u201310.","journal-title":"Springer-Verlag LNCS"},{"key":"28_CR5","unstructured":"H.L. Bodlaender, \u201cPlanar graphs with Bounded Treewidth\u201d, Tech. Rep. No. RUU-CS-88-14, University of Utrecht, 1988."},{"key":"28_CR6","doi-asserted-by":"crossref","first-page":"810","DOI":"10.1007\/BF01759072","volume":"6","author":"M. Chrobak","year":"1991","unstructured":"M. Chrobak and J. Naor, \u201cAn Efficient Parallel Algorithm for Computing a Large Independent Set in a Planar Graph,\u201d Algorithmica, Vol. 6, 1991, pp 810\u2013815.","journal-title":"Algorithmica"},{"key":"28_CR7","doi-asserted-by":"crossref","unstructured":"E. Cohen, \u201cEfficient Parallel Shortest Paths in Digraphs with a Separator Decomposition,\u201d in Proc. Symp. Parallel Algorithms and Architectures (SPAA), 1993, pp 57\u201367.","DOI":"10.1145\/165231.165240"},{"key":"28_CR8","volume-title":"Internetworking with TCP\/IP. Vol. I","author":"D.E. Comer","year":"1991","unstructured":"D.E. Comer, Internetworking with TCP\/IP. Vol. I, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1991."},{"key":"28_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/3-540-57273-2_51","volume":"726","author":"J. Diaz","year":"1993","unstructured":"J. Diaz, J. Toran and M. Serna, \u201cParallel Approximation Schemes for Problems on Planar Graphs\u201d, Proc. First European Symp. on Algorithms (ESA'93), Lecture Notes in Computer Science, Vol. 726, Sept. 1993, pp 145\u2013156.","journal-title":"Lecture Notes in Computer Science"},{"key":"28_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, CA, 1979."},{"key":"28_CR11","unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns, \u201cEvery Problem in MAX SNP has a Parallel Approximation Algorithm\u201d, Tech. Rep. 93-8, Dept, of Computer Science, Univ. at Albany, May 1993."},{"key":"28_CR12","doi-asserted-by":"crossref","unstructured":"H.B. Hunt III, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns, \u201cA Unified Approach to Approximation Schemes for NP-and PSPACE-Hard Problems for Geometric Graphs,\u201d To appear in Proc. Second European Symp. on Algorithms (ESA'94), Sept. 1994.","DOI":"10.1007\/BFb0049428"},{"key":"28_CR13","doi-asserted-by":"crossref","unstructured":"H.B. Hunt III, M.V. Marathe and R.E. Stearns, \u201cGeneralized CNF Satisfiability Problems and Non-Efficient Approximability,\u201d Proc. 9th ACM Conf. on Structure in Complexity Theory, June-July 1994, pp 356\u2013366.","DOI":"10.1109\/SCT.1994.315789"},{"key":"28_CR14","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"V. Kann, \u201cMaximum Bounded 3-Dimensional Matching is MAX SNP-Complete\u201d, Inf. Proc. Lett., Vol. 37, 1991, pp 27\u201335.","journal-title":"Inf. Proc. Lett."},{"key":"28_CR15","volume-title":"Ph.D. Thesis","author":"V. Kann","year":"1992","unstructured":"V. Kann, \u201cOn the Approximability of NP-complete Optimization Problems,\u201d Ph.D. Thesis, Dept. of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, Sweden, May 1992."},{"key":"28_CR16","doi-asserted-by":"crossref","unstructured":"P.N. Klein and S. Subramaniam, \u201cA Linear-Processor Polylog-Time Algorithm for Shortest Paths in Planar Graphs\u201d, Proc. 34th IEEE FOGS, 1993, pp 259\u2013270.","DOI":"10.1109\/SFCS.1993.366861"},{"key":"28_CR17","doi-asserted-by":"crossref","unstructured":"J. Lagergren, \u201cEfficient parallel algorithms for tree-decomposition and related problems\u201d, 31st IEEE FOCS, 1990, pp 173\u2013182.","DOI":"10.1109\/FSCS.1990.89536"},{"issue":"No.2","key":"28_CR18","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"D. Lichtenstein, \u201cPlanar Formulae and their Uses\u201d, SIAM J. Corn-put., Vol 11, No. 2, May 1982, pp 329\u2013343.","journal-title":"SIAM J. Corn-put."},{"key":"28_CR19","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"R.J. Lipton and R.E. Tarjan, \u201cApplications of a Planar Separator Theorem\u201d, SIAM J. Cornput., Vol. 9, 1980, pp 615\u2013627.","journal-title":"SIAM J. Cornput."},{"key":"28_CR20","volume-title":"Annals of Discrete Mathematics, Vol. 32","author":"T. Nishizeki","year":"1988","unstructured":"T. Nishizeki and N. Chiba, Planar Graphs: Theory and Applications, Annals of Discrete Mathematics, Vol. 32, Elsivier Science Publications, Amsterdam, 1988."},{"key":"28_CR21","first-page":"425","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, \u201cOptimization, Approximation and Complexity Classes\u201d JCSS, Vol. 43, 1991, pp 425\u2013440.","journal-title":"JCSS"},{"key":"28_CR22","first-page":"109","volume":"477","author":"V. Radhakrishnan","year":"1992","unstructured":"V. Radhakrishnan, H. B. Hunt III and R. E. Stearns, \u201cEfficient Algorithms for Solving Systems of Linear Equations and Path Problems,\u201d Proc. 9th STACS (Springer-Verlag LNCS Vol. 477), Feb. 1992, pp 109\u2013119.","journal-title":"Springer-Verlag LNCS"},{"key":"28_CR23","doi-asserted-by":"crossref","unstructured":"V. Radhakrishnan, H.B. Hunt,III and R.E. Stearns, \u201cEfficient Algorithms for \u03b4-Near-Planar Graph and Algebraic Problems\u201d, in Complexity in Numerical Optimization, (Edited by P.M. Pardalos), World Scientific Publishing Co., 1993, pp 323\u2013350.","DOI":"10.1142\/9789814354363_0015"},{"key":"28_CR24","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1137\/0211004","volume":"11","author":"A. Rosenthal","year":"1982","unstructured":"A. Rosenthal, \u201cDynamic Programming is Optimal for Nonserial Optimization Problems,\u201d SIAM J. Comput., Vol. 11, 1982, pp 47\u201359.","journal-title":"SIAM J. Comput."},{"key":"28_CR25","volume-title":"Computer-Communication Network Design and Analysis","author":"M. Schwartz","year":"1977","unstructured":"M. Schwartz, Computer-Communication Network Design and Analysis, Prentice Hall, Inc., Englewood Cliffs, NJ, 1977."},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"T. Schaefer, \u201cThe Complexity Of Satisfiability Problems\u201d, Proc. 10th ACMSTOC, 1978, pp 216\u2013226.","DOI":"10.1145\/800133.804350"},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"D. Zuckerman, \u201cNP-Complete Problems have Versions that are Hard to Approximate\u201d, Proc. 8th ACM Conf. on Structure in Complexity Theory, May 1993, pp 305\u2013312.","DOI":"10.1109\/SCT.1993.336517"}],"container-title":["Lecture Notes in Computer Science","Foundation of Software Technology and Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58715-2_136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:38:13Z","timestamp":1742596693000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58715-2_136"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540587156","9783540490548"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-58715-2_136","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}