{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:48:07Z","timestamp":1725475687200},"publisher-location":"Boston, MA","reference-count":15,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387346335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-0-387-34735-6_24","type":"book-chapter","created":{"date-parts":[[2006,12,14]],"date-time":"2006-12-14T18:32:32Z","timestamp":1166121152000},"page":"299-313","source":"Crossref","is-referenced-by-count":1,"title":["On PTAS for Planar Graph Problems"],"prefix":"10.1007","author":[{"given":"Xiuzhen","family":"Huang","sequence":"first","affiliation":[]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s00453-001-0116-5","volume":"33","author":"J. Alber","year":"2002","unstructured":"Alber J, Bodlaender HL, Fernau H, Kloks T, and Niedermeier R (2002) Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33:461\u2013493","journal-title":"Algorithmica"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.jalgor.2004.03.005","volume":"52","author":"J. Alber","year":"2004","unstructured":"Alber J, Fernau H, Niedermeier R (2004) Parameterized complexity: exponential speed-up for planar graph problems. J. Algorithms 52:26\u201356","journal-title":"J. Algorithms"},{"key":"24_CR3","volume-title":"Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties","author":"G. Ausiello","year":"1999","unstructured":"Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, and Protasi M (1999) Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties. New York, Springer-Verlag"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM 41:153\u2013180","journal-title":"Journal of the ACM"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yehuda R and Even S (1982) On approximating a vertex cover for planar graphs. Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp.303\u2013309","DOI":"10.1145\/800070.802205"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"Cai L and Chen J (1997) On fixed-parameter tractability and approximability of NP optimization problems. Journal Of Computer and System Sciences 54:465\u2013474","journal-title":"Journal Of Computer and System Sciences"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"Cai L, Fellows M, Juedes D, Rosamond F (2006) The complexity of polynomialtime approximation. Theory of Computing Systems, to appear.","DOI":"10.1007\/s00224-007-1346-y"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0022-0000(03)00074-6","volume":"67","author":"L. Cai","year":"2003","unstructured":"Cai L and Juedes DW (2003) On the existence of sub-exponential time parameterized algorithms. Journal of Computer and System Sciences 67:789\u2013807","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(97)00164-6","volume":"64","author":"M. Cesati","year":"1997","unstructured":"Cesati M and Trevisan L (1997) On the efficiency of polynomial time approximation schemes. Information Processing Letters 64:165\u2013171","journal-title":"Information Processing Letters"},{"key":"24_CR10","unstructured":"Chert J, Chor B, Fellows M, Huang X, Juedes DW, Kanj I and Xia G (2004) Tight lower bounds for parameterized NP-hard problems. Proc. of the 19th Annual IEEE Conference on Computational Complexity, pp. 150\u2013160"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Chen J, Huang X, Kanj I and Xia G (2004) Linear FPT reductions and computational lower bounds. Proc. of the 36th ACM Symposium on Theory of Computing, pp. 212\u2013221","DOI":"10.1145\/1007352.1007391"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J. Chen","year":"2001","unstructured":"Chen J, Kanj I, and Jia W (2001) Vertex cover: further observations and further improvements. Journal of Algorithms 41:280\u2013301","journal-title":"Journal of Algorithms"},{"key":"24_CR13","unstructured":"Chen J, Kanj I, Xia G (2003) A note on parameterized exponential time complexity. Tech. Report, DePaul University"},{"key":"24_CR14","volume-title":"Graph theory","author":"R. Diestel","year":"2000","unstructured":"Diestel R (2000) Graph theory. New York: Springer"},{"key":"24_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parmneterized complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey RG and Fellows MR (1999) Parmneterized complexity. Springer, New York"}],"container-title":["IFIP International Federation for Information Processing","Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-34735-6_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,9]],"date-time":"2023-05-09T23:50:34Z","timestamp":1683676234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-34735-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9780387346335"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-34735-6_24","relation":{},"subject":[]}}