{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T20:21:37Z","timestamp":1725740497053},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_39","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T01:36:30Z","timestamp":1373506590000},"page":"451-462","source":"Crossref","is-referenced-by-count":1,"title":["When Is Weighted Satisfiability FPT?"],"prefix":"10.1007","author":[{"given":"Iyad A.","family":"Kanj","sequence":"first","affiliation":[]},{"given":"Ge","family":"Xia","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","unstructured":"Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: Proceedings of UAI, pp. 7\u201315. Morgan Kaufmann (2001)"},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Fomin, F., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.: (Meta) kernelization. In: Proceedings of FOCS, pp. 629\u2013638 (2009)","DOI":"10.1109\/FOCS.2009.46"},{"issue":"3","key":"39_CR3","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/s00224-007-1346-y","volume":"41","author":"L. Cai","year":"2007","unstructured":"Cai, L., Fellows, M., Juedes, D., Rosamond, F.: The complexity of polynomial-time approximation. Theory of Computing Systems\u00a041(3), 459\u2013477 (2007)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"39_CR4","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.dam.2006.04.040","volume":"155","author":"J. Chen","year":"2007","unstructured":"Chen, J., Huang, X., Kanj, I., Xia, G.: Polynomial time approximation schemes and parameterized complexity. Discrete Appl. Math.\u00a0155(2), 180\u2013193 (2007)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"39_CR5","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.jcss.2006.11.001","volume":"73","author":"J. Chen","year":"2007","unstructured":"Chen, J., Kanj, I., Perkovic, L., Sedgwick, E., Xia, G.: Genus characterizes the complexity of certain graph problems: Some tight results. Journal of Computer and System Sciences\u00a073(6), 892\u2013907 (2007)","journal-title":"Journal of Computer and System Sciences"},{"key":"39_CR6","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1145\/1101821.1101823","volume":"52","author":"E. Demaine","year":"2005","unstructured":"Demaine, E., Fomin, F., Hajiaghayi, M., Thilikos, D.: Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. J. ACM\u00a052, 866\u2013893 (2005)","journal-title":"J. ACM"},{"key":"39_CR7","unstructured":"Demaine, E., Hajiaghayi, M.: Bidimensionality: new connections between FPT algorithms and PTASs. In: Proceedings of SODA, pp. 590\u2013601 (2005)"},{"issue":"2","key":"39_CR8","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1137\/040616929","volume":"20","author":"E. Demaine","year":"2006","unstructured":"Demaine, E., Hajiaghayi, M., Thilikos, D.: The bidimensional theory of bounded-genus graphs. SIAM J. Discrete Math.\u00a020(2), 357\u2013371 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR9","doi-asserted-by":"publisher","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, New York (1999)"},{"key":"39_CR10","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2010","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2010)"},{"key":"39_CR11","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Raman, V., Saurabh, S.: Bidimensionality and EPTAS. In: Proceedings of SODA, pp. 748\u2013759 (2011)","DOI":"10.1137\/1.9781611973082.59"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Thilikos, D.: Bidimensionality and kernels. In: Proceedings of SODA, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"39_CR13","volume-title":"Topological graph theory","author":"J. Gross","year":"1987","unstructured":"Gross, J., Tucker, T.: Topological graph theory. Wiley-Interscience, NY (1987)"},{"issue":"6","key":"39_CR14","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1016\/j.jcss.2010.09.001","volume":"77","author":"I. Kanj","year":"2011","unstructured":"Kanj, I., Pelsmajer, M., Schaefer, M., Xia, G.: On the induced matching problem. Journal of Computers and System Sciences\u00a077(6), 1058\u20131070 (2011)","journal-title":"Journal of Computers and System Sciences"},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Khanna, S., Motwani, R.: Towards a syntactic characterization of PTAS. In: Proceedings of STOC, pp. 468\u2013477 (1996)","DOI":"10.1145\/237814.237979"},{"issue":"1","key":"39_CR16","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.jcss.2012.09.001","volume":"79","author":"D. Marx","year":"2013","unstructured":"Marx, D.: Completely inapproximable monotone and antimonotone parameterized problems. J. Comput. Syst. Sci.\u00a079(1), 144\u2013151 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"39_CR17","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"Robertson, N., Seymour, P.D.: Graph minors X: Obstructions to tree-decomposition. J. Comb. Theory, Ser. B\u00a052(2), 153\u2013190 (1991)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"39_CR18","doi-asserted-by":"crossref","unstructured":"Savage, J.: Planar circuit complexity and the performance of VLSI algorithms. Technical Report RR-0077, INRIA (May 1981)","DOI":"10.1007\/978-3-642-68402-9_8"},{"key":"39_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Theory and Applications of Satisfiability Testing","author":"S. Szeider","year":"2004","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of sat. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 188\u2013202. Springer, Heidelberg (2004)"},{"key":"39_CR20","volume-title":"Introduction to graph theory","author":"D. West","year":"1996","unstructured":"West, D.: Introduction to graph theory. Prentice Hall Inc., NJ (1996)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T14:25:17Z","timestamp":1557930317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}