{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:09:22Z","timestamp":1725548962350},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_22","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"269-280","source":"Crossref","is-referenced-by-count":12,"title":["Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Fernau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"22_CR1","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M., Niedermeier, R.: Polynomial-time data reduction for dominating set. Journal of the ACM\u00a051(3), 363\u2013384 (2004)","journal-title":"Journal of the ACM"},{"key":"22_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.: Parameterized complexity: exponential speedup for planar graph problems. Journal of Algorithms\u00a052, 26\u201356 (2004)","journal-title":"Journal of Algorithms"},{"key":"22_CR3","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1016\/S0022-0000(03)00072-2","volume":"67","author":"J. Alber","year":"2003","unstructured":"Alber, J., Fernau, H., Niedermeier, R.: Graph separators: a parameterized view. Journal of Computer and System Sciences\u00a067, 808\u2013832 (2003)","journal-title":"Journal of Computer and System Sciences"},{"key":"22_CR4","first-page":"27","volume":"25","author":"R. Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda, R., Even, S.: A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Discrete Mathematics\u00a025, 27\u201346 (1985)","journal-title":"Annals of Discrete Mathematics"},{"key":"22_CR5","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.A., Jia, W.: Vertex cover: further observations and further improvement. Journal of Algorithms\u00a041, 280\u2013301 (2001)","journal-title":"Journal of Algorithms"},{"key":"#cr-split#-22_CR6.1","doi-asserted-by":"crossref","unstructured":"Dinur, I., Safra, S.: On the importance of Being Biased (1.36 hardness of approximating Vertex-Cover). In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 33\u201342 (2002);","DOI":"10.1145\/509907.509915"},{"key":"#cr-split#-22_CR6.2","unstructured":"To appear in Annals of Mathematics"},{"key":"22_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. Downey","year":"1999","unstructured":"Downey, R., Fellows, M.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Downey, R., Fellows, M., Stege, U.: Parameterized Complexity: A Framework for Systematically Confronting Computational Intractability. In: Graham, R., Kratochv\u00edl, J., Ne\u0161et\u0159il, J., Roberts, F. (eds.) Proceedings of the DIMACS-DIMATIA Workshop, Prague 1997. AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a049, pp. 49\u201399 (1999)","DOI":"10.1090\/dimacs\/049\/04"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"Fellows, M.: Parameterized complexity: the main ideas and connections to practical computing. Electronic Notes in Theoretical Computer Science\u00a061 (2002)","DOI":"10.1016\/S1571-0661(04)00301-9"},{"key":"22_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/3-540-44450-5_19","volume-title":"FST TCS 2000: Foundations of Software Technology and Theoretical Science","author":"M. Fellows","year":"2000","unstructured":"Fellows, M., McCartin, C., Rosamond, F., Stege, U.: Coordinatized Kernels and Catalytic Reductions: An Improved FPT Algorithm for Max Leaf Spanning Tree and Other Problems. In: Kapoor, S., Prasad, S. (eds.) FST TCS 2000. LNCS, vol.\u00a01974, pp. 240\u2013251. Springer, Heidelberg (2000)"},{"key":"22_CR11","first-page":"109","volume":"8","author":"H. Gr\u00f6tzsch","year":"1959","unstructured":"Gr\u00f6tzsch, H.: Ein Dreifarbensatz f\u00fcr dreikreisfreie Netze auf der Kugel. Wiss. Zeitschrift der Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss., Reihe\u00a08, 109\u2013120 (1959)","journal-title":"Wiss. Zeitschrift der Martin-Luther-Univ. Halle-Wittenberg, Math.-Naturwiss., Reihe"},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"997","DOI":"10.1016\/S0304-3975(01)00414-5","volume":"289","author":"S. Khot","year":"2002","unstructured":"Khot, S., Raman, V.: Parameterized complexity of finding subgraphs with hereditary properties. Theoretical Computer Science\u00a0289, 997\u20131008 (2002)","journal-title":"Theoretical Computer Science"},{"key":"22_CR13","volume-title":"Theory of Graphs, Colloquium Publications XXXVIII","author":"O. Ore","year":"1962","unstructured":"Ore, O.: Theory of Graphs, Colloquium Publications XXXVIII. American Mathematical Society, Providence (1962)"},{"key":"22_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"474","DOI":"10.1007\/978-3-540-45078-8_41","volume-title":"Algorithms and Data Structures","author":"E. Prieto","year":"2003","unstructured":"Prieto, E., Sloper, C.: Either\/or: Using vertex cover structure in designing FPT-algorithms-the case of k-internal spanning tree. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol.\u00a02748, pp. 474\u2013483. Springer, Heidelberg (2003)"},{"key":"22_CR15","unstructured":"Uehara, R.: Probabilistic Algorithms and Complexity Classes, PhD thesis, Department of Computer Science and Information Mathematics, The University of Electro-Communications, Japan (March 1998)"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T18:13:46Z","timestamp":1685470426000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}