{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:09:15Z","timestamp":1763467755323},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540390985"},{"type":"electronic","value":"9783540391012"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11847250_10","type":"book-chapter","created":{"date-parts":[[2006,9,13]],"date-time":"2006-09-13T15:43:02Z","timestamp":1158162182000},"page":"109-120","source":"Crossref","is-referenced-by-count":35,"title":["On Parameterized Approximability"],"prefix":"10.1007","author":[{"given":"Yijia","family":"Chen","sequence":"first","affiliation":[]},{"given":"Martin","family":"Grohe","sequence":"additional","affiliation":[]},{"given":"Magdalena","family":"Gr\u00fcber","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"10_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"key":"10_CR2","volume-title":"Complexity and Approximation","author":"G. Ausiello","year":"2003","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation. Springer, Heidelberg (2003)"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s001530050069","volume":"36","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: On the parameterized complexity of short computation and factorization. Archive for Mathematical Logic\u00a036, 321\u2013337 (1997)","journal-title":"Archive for Mathematical Logic"},{"key":"10_CR4","unstructured":"Cai, L., Huang, X.: Fixed-Parameter Approximation: Conceptual Framework and Approximability Results. These proceedings"},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1002\/malq.19970430204","volume":"43","author":"M. Cesati","year":"1997","unstructured":"Cesati, M., Di Ianni, M.: Computation models for parameterized complexity. Mathematical Logic Quarterly\u00a043, 179\u2013202 (1997)","journal-title":"Mathematical Logic Quarterly"},{"key":"10_CR6","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. In: Proceedings of the 19th IEEE Conference on Computational Complexity, pp. 150\u2013160 (2004)"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BFb0017394","volume-title":"Graph Grammars and Their Application to Computer Science","author":"B. Courcelle","year":"1991","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Context-free handle-rewriting hypergraph grammars. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol.\u00a0532, pp. 253\u2013268. Springer, Heidelberg (1991)"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The PCP theorem by gap amplification. In: Proceedings of STOC 2006. 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA (to appear, 2006)","DOI":"10.1145\/1132516.1132553"},{"key":"10_CR9","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness II: On completeness for W[1]. Journal of Theoretical Computer Science\u00a0141, 109\u2013131 (1995)","journal-title":"Journal of Theoretical Computer Science"},{"key":"10_CR10","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"key":"10_CR11","unstructured":"Downey, R.G., Fellows, M.R., McCartin, C.: Parameterized Approximation Algorithms. These proceedings"},{"issue":"2","key":"10_CR12","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/PL00009191","volume":"20","author":"G. Even","year":"1998","unstructured":"Even, G., Naor, J.S., Schieber, B., Sudan, M.: Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica\u00a020(2), 151\u2013174 (1998)","journal-title":"Algorithmica"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Fellows, M., Rosamond, F., Rotics, U., Szeider, S.: Clique-width minimization is NP-hard. In: Proceedings of STOC 2006. 38th ACM Symposium on Theory of Computing, Seattle, Washington, USA (to appear, 2006)","DOI":"10.1145\/1132516.1132568"},{"key":"10_CR14","volume-title":"Parameterized Complexity Theory","author":"J. Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Heidelberg (2006)"},{"key":"10_CR15","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                        1\u2009\u2212\u2009\u03b5\n                        . Electronic Colloquium on Computational Complexity, Report TR97-038 (1997)"},{"key":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/11604686_5","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"S. Oum","year":"2005","unstructured":"Oum, S.: Approximating rank-width and clique-width quickly. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 49\u201358. Springer, Heidelberg (2005)"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Oum, S., Seymour, P.: Approximating clique-width and branch-width. Journal of Combinatorial Theory, Series B (to appear)","DOI":"10.1016\/j.jctb.2005.10.006"},{"issue":"4","key":"10_CR18","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/BF01271272","volume":"16","author":"B. Reed","year":"1996","unstructured":"Reed, B., Robertson, N., Seymour, P., Thomas, R.: Packing directed circuits. Combinatorica\u00a016(4), 535\u2013554 (1996)","journal-title":"Combinatorica"},{"issue":"2","key":"10_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF01200760","volume":"15","author":"P. Seymour","year":"1995","unstructured":"Seymour, P.: Packing directed circuits fractionally. Combinatorica\u00a015(2), 281\u2013288 (1995)","journal-title":"Combinatorica"},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-39658-1_44","volume-title":"Algorithms - ESA 2003","author":"A. Slivkins","year":"2003","unstructured":"Slivkins, A.: Parameterized tractability of edge-disjoint paths on directed acyclic graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 482\u2013493. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11847250_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:18:38Z","timestamp":1619507918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11847250_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540390985","9783540391012"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11847250_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}