{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:04Z","timestamp":1759639024259},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540584346"},{"type":"electronic","value":"9783540487944"}],"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\/bfb0049428","type":"book-chapter","created":{"date-parts":[[2006,3,6]],"date-time":"2006-03-06T13:42:35Z","timestamp":1141652555000},"page":"424-435","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs"],"prefix":"10.1007","author":[{"suffix":"III","given":"H. B.","family":"Hunt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. V.","family":"Marathe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"D. J.","family":"Rosenkrantz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V.","family":"Radhakrishnan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. E.","family":"Stearns","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,2,23]]},"reference":[{"key":"38_CR1","doi-asserted-by":"crossref","unstructured":"B.S. Baker, \u201cApproximation Algorithms for NP-complete problems on Planar Graphs,\u201d 24th IEEE Symposium on Foundations of Computer Science (FOCS), 1983, pp 265\u2013273.","DOI":"10.1109\/SFCS.1983.7"},{"key":"38_CR2","first-page":"127","volume":"1","author":"J.L. Bentley","year":"1983","unstructured":"J.L. Bentley, T. Ottmann and P. Widmayer, \u201cThe Complexity of Manipulating Hierarchically Defined set of Intervals,\u201d Advances in Computing Research, ed. F.P. Preparata Vol. 1, (1983), pp. 127\u2013158.","journal-title":"Advances in Computing Research, ed. F.P. Preparata"},{"key":"38_CR3","doi-asserted-by":"crossref","unstructured":"A. Condon, J. Feigenbaum, C. Lund and P. Shor, \u201cProbabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions\u201d, in Proc. 25th Annual ACM Symposium on Theory Of Computing, (STOC), 1993, pp. 305\u2013313.","DOI":"10.1145\/167088.167190"},{"key":"38_CR4","unstructured":"A. Condon, J. Feigenbaum, C. Lund and P. Shor, \u201cRandom Debators and the Hardness of Approximating Stochastic functions for PSPACE-Hard Functions\u201d, to appear in 9th Annual IEEE Annual Conference on Structure in Complexity Theory, June 1994."},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"B.N. Clark, C.J. Colbourn, and D.S. Johnson, \u201cUnit Disk Graphs,\u201d Discrete Math., Vol. 86, 1990, pp. 165\u2013177.","journal-title":"Discrete Math."},{"key":"38_CR6","doi-asserted-by":"crossref","unstructured":"J. Diaz, M.J. Serna and J. Toran, \u201cParallel Approximation Schemes for problems on planar graphs,\u201d 1st European Symposium on Algorithms (ESA '93), 1993, pp 145\u2013156.","DOI":"10.1007\/3-540-57273-2_51"},{"key":"38_CR7","doi-asserted-by":"crossref","unstructured":"D. Eppstein, G.L. Miller and S.H. Teng, \u201cA Deterministic Linear Time Algorithm for Geometric Separators and its Application,\u201d 9th ACM Symposium on Computational Geometry, pp 99\u2013108, 1993.","DOI":"10.1145\/160985.161005"},{"key":"38_CR8","doi-asserted-by":"crossref","unstructured":"T. Feder and D. Greene, \u201cOptimal Algorithms for Approximate Clustering,\u201d 30th ACM Symposium on Theory Of Computing (STOC), pp 434\u2013444, 1988.","DOI":"10.1145\/62212.62255"},{"issue":"No.3","key":"38_CR9","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0020-0190(81)90111-3","volume":"12","author":"R.J. Fowler","year":"1981","unstructured":"R.J. Fowler, M.S. Paterson and S.L. Tanimoto, \u201cOptimal Packing and Covering in the Plane are NP-Complete,\u201d Inf. Proc. Letters, Vol 12, No.3, June 1981, pp. 133\u2013137.","journal-title":"Inf. Proc. Letters"},{"key":"38_CR10","doi-asserted-by":"crossref","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"W.K. Hale","year":"1980","unstructured":"W.K. Hale, \u201cFrequency Assignment: Theory and Applications,\u201d Proc. IEEE, Vol. 68, 1980, pp 1497\u20131514.","journal-title":"Proc. IEEE"},{"issue":"No.1","key":"38_CR11","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"D.S. Hochbaum and W. Maass, \u201cApproximation Schemes for Covering and Packing Problems in Image Processing and VLSI,\u201d JACM, Vol 32, No. 1, 1985, pp 130\u2013136.","journal-title":"JACM"},{"key":"38_CR12","doi-asserted-by":"crossref","unstructured":"T.Jiang and L. Wang, \u201cAn Approximation Scheme for Some Steiner Tree Problems in the Plane,\u201d to appear in Fifth Annual International Symposium on Algorithms and Computation (ISAAC), 1994.","DOI":"10.1007\/3-540-58325-4_206"},{"key":"38_CR13","unstructured":"H.B. Hunt III, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, \u201cEvery problem in MAX SNP has a parallel approximation algorithm,\u201d Technical Report No 8, University at Albany, May 1993."},{"key":"38_CR14","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 Technical Report No 93-17, University at Albany, June 1994.","DOI":"10.1007\/BFb0049428"},{"issue":"No.6","key":"38_CR15","doi-asserted-by":"crossref","first-page":"1063","DOI":"10.1137\/0217068","volume":"17","author":"T. Lengauer","year":"1988","unstructured":"T. Lengauer and E. Wanke, \u201cEfficient Solutions for Connectivity Problems for Hierarchically Defined Graphs,\u201d SIAM J. Computing, Vol. 17, No. 6, 1988, pp. 1063\u20131080.","journal-title":"SIAM J. Computing"},{"issue":"No.2","key":"38_CR16","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1137\/0136016","volume":"32","author":"R. Lipton","year":"1979","unstructured":"R. Lipton and R. E. Tarjan, \u201cA Separator Theorem for Planar Graphs,\u201d SIAM J. Appl. Math., Vol. 32, No. 2, April 1979, pp 177\u2013189.","journal-title":"SIAM J. Appl. Math."},{"key":"38_CR17","unstructured":"M.V. Marathe H.B. Hunt III and S.S. Ravi, \u201cGeometric Heuristics for Unit Disk Graphs\u201d, in the proceedings of 4th Canadian Conference on Computational Geometry, 1992, pp. 244\u2013249."},{"key":"38_CR18","doi-asserted-by":"crossref","unstructured":"M.V. Marathe H.B. Hunt III and S.S. Ravi, \u201cThe Complexity of Approximating PSPACE-Complete Problems for Hierarchical Specifications\u201d, in the proceedings of ICALP'93, 1993, pp 76\u201387.","DOI":"10.1007\/3-540-56939-1_63"},{"key":"38_CR19","doi-asserted-by":"crossref","unstructured":"M.V. Marathe, V. Radhakrishnan, H.B. Hunt III and S.S. Ravi, \u201cHierarchically Specified Unit Disk Graphs\u201d, to appear in the proceedings of WG'93, 1993.","DOI":"10.1007\/3-540-57899-4_38"},{"key":"38_CR20","doi-asserted-by":"crossref","unstructured":"M.V. Marathe, H.B. Hunt III, R.E. Stearns and V. Radhakrishnan, \u201cApproximation schemes for PSPACE-Complete problems for succinct graphs,\u201d to appear in Proceedings of 26th Annual ACM Symposium on the Theory of Computing (STOC), May 1994.","DOI":"10.1145\/195058.195233"},{"key":"38_CR21","unstructured":"C. Mead and L. Conway, Introduction to VLSI Systems, Addison Wesley, 1980."},{"issue":"No.1","key":"38_CR22","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Meggido","year":"1984","unstructured":"N. Meggido and K Supowit, \u201cOn The Complexity Of Some Common Geometric Location Problems,\u201d SIAM Journal Of Computing, Vol 13, No.1, February 1984, pp. 182\u2013196.","journal-title":"SIAM Journal Of Computing"},{"key":"38_CR23","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"No.43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis, \u201cOptimization, Approximation and Complexity Classes\u201d Journal of Computer and System Sciences, No.43, 1991, pp. 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"38_CR24","volume-title":"Ph.D. thesis","author":"S. Ramanathan","year":"1993","unstructured":"S. Ramanathan Scheduling Algorithms for Multi-Hop Radio Networks, Ph.D. thesis, Department of Computer Science, University of Delaware, Newark, 1993."},{"key":"38_CR25","series-title":"CMU-CS-91-184","volume-title":"Ph.D. thesis","author":"S.H. Teng","year":"1991","unstructured":"S.H. Teng, Points, Spheres, and Separators, A Unified Geometric Approach to Graph Separators, Ph.D. thesis, School of Computer Science, Carnegie Mellon University, CMU-CS-91-184, Pittsburgh, August 1991."},{"issue":"No.6","key":"38_CR26","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(88)90174-3","volume":"28","author":"D.W. Wong","year":"1988","unstructured":"D.W. Wong and Y.S. Kuo, \u201cA Study of Two Geometric Location Problems,\u201d Inf. Proc. Letters, Vol. 28, No. 6, Aug. 1988, pp 281\u2013286.","journal-title":"Inf. Proc. Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '94"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0049428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,30]],"date-time":"2020-01-30T02:59:57Z","timestamp":1580353197000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0049428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540584346","9783540487944"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/bfb0049428","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":"23 February 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}