{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:55:43Z","timestamp":1725569743454},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642169250"},{"type":"electronic","value":"9783642169267"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-16926-7_15","type":"book-chapter","created":{"date-parts":[[2010,11,10]],"date-time":"2010-11-10T02:48:26Z","timestamp":1289357306000},"page":"147-158","source":"Crossref","is-referenced-by-count":7,"title":["Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs"],"prefix":"10.1007","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Jakub Onufry","family":"Wojtaszczyk","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-540-73545-8_39","volume-title":"Computing and Combinatorics","author":"N. Alon","year":"2007","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. In: Lin, G. (ed.) COCOON 2007. LNCS, vol.\u00a04598, pp. 394\u2013405. Springer, Heidelberg (2007)"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 563\u2013574. Springer, Heidelberg (2008)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M. (Meta) kernelization. In: Proc. of FOCS 2009, pp. 629\u2013638 (2009)","DOI":"10.1109\/FOCS.2009.46"},{"key":"15_CR4","unstructured":"Bodlaender, H.L., Thomasse, S., Yeo, A.: Analysis of data reduction: Transformations give evidence for non-existence of polynomial kernels, technical Report UU-CS-2008-030, Institute of Information and Computing Sciences, Utrecht University, Netherlands (2008)"},{"issue":"2","key":"15_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 improvements. J. Algorithms\u00a041(2), 280\u2013301 (2001)","journal-title":"J. Algorithms"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Proc. of ICALP 2009, pp. 378\u2013389 (2009)","DOI":"10.1007\/978-3-642-02927-1_32"},{"key":"15_CR7","doi-asserted-by":"publisher","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), http:\/\/citeseer.ist.psu.edu\/downey98parameterized.html"},{"key":"15_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1007\/978-3-540-74839-7_20","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Escoffier","year":"2007","unstructured":"Escoffier, B., Gourv\u00e8s, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem. In: Brandst\u00e4dt, A., Kratsch, D., M\u00fcller, H. (eds.) WG 2007. LNCS, vol.\u00a04769, pp. 202\u2013213. Springer, Heidelberg (2007)"},{"key":"15_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-73420-8_31","volume-title":"Automata, Languages and Programming","author":"M.R. Fellows","year":"2007","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 340\u2013351. Springer, Heidelberg (2007)"},{"key":"15_CR10","unstructured":"Fernau, H., Fomin, F.V., Lokshtanov, D., Raible, D., Saurabh, S., Villanger, Y.: Kernel(s) for problems with no kernel: On out-trees with many leaves. In: Proc. of STACS 2009, pp. 421\u2013432 (2009)"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Proc. of SODA 2010, pp. 503\u2013510 (2010)","DOI":"10.1137\/1.9781611973075.43"},{"key":"15_CR12","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proc. of STOC 2008, pp. 133\u2013142 (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-92248-3_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P.A. Golovach","year":"2008","unstructured":"Golovach, P.A., Villanger, Y.: Parameterized complexity for domination problems on degenerate graphs. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol.\u00a05344, pp. 195\u2013205. Springer, Heidelberg (2008)"},{"issue":"4","key":"15_CR14","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF02579141","volume":"4","author":"A.V. Kostochka","year":"1984","unstructured":"Kostochka, A.V.: Lower bound of the hadwiger number of graphs by their average degree. Combinatorica\u00a04(4), 307\u2013316 (1984)","journal-title":"Combinatorica"},{"key":"15_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-3-642-11440-3_25","volume-title":"WALCOM: Algorithms and Computation","author":"N. Misra","year":"2010","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S., Sikdar, S.: FPT Algorithms for Connected Feedback Vertex Set. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.\u00a05942, pp. 269\u2013280. Springer, Heidelberg (2010)"},{"key":"15_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1007\/978-3-642-04128-0_62","volume-title":"Algorithms - ESA 2009","author":"G. Philip","year":"2009","unstructured":"Philip, G., Raman, V., Sikdar, S.: Solving dominating set in larger classes of graphs: Fpt algorithms and polynomial kernels. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 694\u2013705. Springer, Heidelberg (2009)"},{"issue":"2","key":"15_CR17","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1017\/S0305004100061521","volume":"95","author":"A. Thomason","year":"1984","unstructured":"Thomason, A.: An extremal function for contractions of graphs. Math. Proc. Cambridge Philos. Soc.\u00a095(2), 261\u2013265 (1984)","journal-title":"Math. Proc. Cambridge Philos. Soc."},{"issue":"2","key":"15_CR18","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1006\/jctb.2000.2013","volume":"81","author":"A. Thomason","year":"2001","unstructured":"Thomason, A.: The extremal function for complete minors. J. Comb. Theory, Ser. B\u00a081(2), 318\u2013338 (2001)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Thomass\u00e9, S.: A quadratic kernel for feedback vertex set. In: Proc. of SODA 2009, pp. 115\u2013119 (2009)","DOI":"10.1137\/1.9781611973068.13"}],"container-title":["Lecture Notes in Computer Science","Graph Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-16926-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T01:06:04Z","timestamp":1559783164000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-16926-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642169250","9783642169267"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-16926-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}