{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:08Z","timestamp":1759638368503},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2012,8,23]],"date-time":"2012-08-23T00:00:00Z","timestamp":1345680000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s00453-012-9681-z","type":"journal-article","created":{"date-parts":[[2012,8,22]],"date-time":"2012-08-22T11:56:10Z","timestamp":1345636570000},"page":"504-530","source":"Crossref","is-referenced-by-count":6,"title":["The Kernelization Complexity of Connected Domination in Graphs with (no) Small Cycles"],"prefix":"10.1007","volume":"68","author":[{"given":"Neeldhara","family":"Misra","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Geevarghese","family":"Philip","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,8,23]]},"reference":[{"issue":"3","key":"9681_CR1","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/990308.990309","volume":"51","author":"J. Alber","year":"2004","unstructured":"Alber, J., Fellows, M.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. J. ACM 51(3), 363\u2013384 (2004)","journal-title":"J. ACM"},{"key":"9681_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity\u2014A\u00a0Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity\u2014A\u00a0Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9681_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1007\/978-3-540-70575-8_46","volume-title":"Automata, Languages and Programming, 35th International Colloquium, ICALP2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games","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.) Automata, Languages and Programming, 35th International Colloquium, ICALP2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, Reykjavik, Iceland, July 7\u201311, 2008. Lecture Notes in Computer Science, vol. 5125, pp. 563\u2013574. Springer, Berlin (2008)"},{"issue":"8","key":"9681_CR4","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/j.jcss.2009.04.001","volume":"75","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Downey, R.G., Fellows, M.R., Hermelin, D.: On problems without polynomial kernels. J. Comput. Syst. Sci. 75(8), 423\u2013434 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9681_CR5","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1109\/FOCS.2009.46","volume-title":"50th Annual IEEE Symposium on Foundations of Computer Science, FOCS2009","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) kernelization. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS2009, Atlanta, Georgia, USA, October 25\u201327, 2009 pp. 629\u2013638. IEEE Computer Society, Los Alamitos (2009)"},{"issue":"35","key":"9681_CR6","doi-asserted-by":"crossref","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"H.L. Bodlaender","year":"2011","unstructured":"Bodlaender, H.L., Thomass\u00e9, S., Yeo, A.: Kernel bounds for disjoint cycles and disjoint paths. Theor. Comput. Sci. 412(35), 4570\u20134578 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9681_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/978-3-642-16926-7_15","volume-title":"Graph Theoretic Concepts in Computer Science\u201436th International Workshop, WG2010","author":"M. Cygan","year":"2010","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Kernelization hardness of connectivity problems in d-degenerate graphs. In: Thilikos, D.M. (ed.) Graph Theoretic Concepts in Computer Science\u201436th International Workshop, WG2010, Zar\u00f3s, Crete, Greece, June 28\u201330, 2010. Lecture Notes in Computer Science, vol. 6410, pp. 147\u2013158. Springer, Berlin (2010). Revised Papers"},{"key":"9681_CR8","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"157","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS2009","author":"A. Dawar","year":"2009","unstructured":"Dawar, A., Kreutzer, S.: Domination problems in nowhere-dense classes. In: Kannan, R., Kumar, K.N. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS2009. Leibniz International Proceedings in Informatics (LIPIcs), vol. 4, pp. 157\u2013168. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl (2009)"},{"key":"9681_CR9","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"9681_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/978-3-642-02927-1_32","volume-title":"Automata, Languages and Programming, 36th International Colloquium, ICALP2009, Proceedings, Part\u00a0I","author":"M. Dom","year":"2009","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Incompressibility through colors and IDs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Automata, Languages and Programming, 36th International Colloquium, ICALP2009, Proceedings, Part\u00a0I, Rhodes, Greece, July 5\u201312, 2009. Lecture Notes in Computer Science, vol. 5555, pp. 378\u2013389. Springer, Berlin (2009)"},{"key":"9681_CR11","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, Berlin (1999)"},{"key":"9681_CR12","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"S.E. Dreyfus","year":"1972","unstructured":"Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195\u2013207 (1972)","journal-title":"Networks"},{"key":"9681_CR13","unstructured":"Fernau, H.: Parameterized algorithmics: a graph-theoretic approach. Habilitationsschrift, Universit\u00e4t T\u00fcbingen, Germany (2005)"},{"key":"9681_CR14","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1137\/1.9781611973075.43","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA2010","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Thilikos, D.M.: Bidimensionality and kernels. In: Charikar,\u00a0M. (ed.) Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA2010, Austin, Texas, USA, January 17\u201319, 2010, pp. 503\u2013510. SIAM, Philadelphia (2010)"},{"key":"9681_CR15","first-page":"133","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Dwork, C. (ed.) Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17\u201320, 2008, pp. 133\u2013142. ACM, New York (2008)"},{"key":"9681_CR16","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/j.jcss.2010.06.007","volume":"77","author":"L. Fortnow","year":"2011","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. J. Comput. Syst. Sci. 77, 91\u2013106 (2011)","journal-title":"J. Comput. Syst. Sci."},{"key":"9681_CR17","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)"},{"key":"9681_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/978-3-540-92248-3_18","volume-title":"Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG2008","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.) Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG2008, Durham, UK, June\u00a030\u2013July\u00a02, 2008. Lecture Notes in Computer Science, vol. 5344, pp. 195\u2013205. Springer, Berlin (2008). Revised Papers"},{"key":"9681_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/978-3-642-12200-2_4","volume-title":"LATIN2010: Theoretical Informatics, 9th Latin American Symposium, Proceedings","author":"Q. Gu","year":"2010","unstructured":"Gu, Q., Imani, N.: Connectivity is not a limit for kernelization: planar connected dominating set. In: L\u00f3pez-Ortiz, A. (ed.) LATIN2010: Theoretical Informatics, 9th Latin American Symposium, Proceedings, Oaxaca, Mexico, April 19\u201323, 2010. Lecture Notes in Computer Science, vol. 6034, pp. 26\u201337. Springer, Berlin (2010)"},{"issue":"1","key":"9681_CR20","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"key":"9681_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/978-3-642-22006-7_39","volume-title":"Automata, Languages and Programming\u201438th International Colloquium, ICALP2011, Proceedings, Part\u00a0I","author":"D. Hermelin","year":"2011","unstructured":"Hermelin, D., Mnich, M., van Leeuwen, E.J., Woeginger, G.J.: Domination when the Stars are out. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages and Programming\u201438th International Colloquium, ICALP2011, Proceedings, Part\u00a0I, Zurich, Switzerland, July 4\u20138, 2011. Lecture Notes in Computer Science, vol. 6755, pp. 462\u2013473. Springer, Berlin (2011)"},{"key":"9681_CR22","series-title":"The IBM Research Symposia Series","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proceedings of a Symposium on the Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, IBM Thomas J. Watson Research Center, Yorktown Heights, New York, March 20\u201322, 1972. The IBM Research Symposia Series, pp. 85\u2013103. Plenum, New York (1972)"},{"key":"9681_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-642-02017-9_31","volume-title":"Theory and Applications of Models of Computation, 6th Annual Conference, TAMC2009, Proceedings","author":"D. Lokshtanov","year":"2009","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: Linear kernel for planar connected dominating set. In: Chen, J., Cooper, S.B. (eds.) Theory and Applications of Models of Computation, 6th Annual Conference, TAMC2009, Proceedings, Changsha, China, May 18\u201322, 2009. Lecture Notes in Computer Science, vol. 5532, pp. 281\u2013290. Springer, Berlin (2009)"},{"issue":"23","key":"9681_CR24","doi-asserted-by":"crossref","first-page":"2536","DOI":"10.1016\/j.tcs.2010.10.045","volume":"412","author":"D. Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: A linear kernel for a planar connected dominating set. Theor. Comput. Sci. 412(23), 2536\u20132543 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"9681_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/978-3-642-20877-5_8","volume-title":"Theory and Applications of Models of Computation\u20148th Annual Conference, TAMC2011, Proceedings","author":"W. Luo","year":"2011","unstructured":"Luo, W., Wang, J., Feng, Q., Guo, J., Chen, J.: An improved kernel for planar connected dominating set. In: Ogihara, M., Tarui, J. (eds.) Theory and Applications of Models of Computation\u20148th Annual Conference, TAMC2011, Proceedings, Tokyo, Japan, May 23\u201325, 2011. Lecture Notes in Computer Science, vol. 6648, pp. 70\u201381. Springer, Berlin (2011)"},{"key":"9681_CR26","series-title":"Leibniz International Proceedings in Informatics (LIPIcs)","first-page":"96","volume-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS2010","author":"N. Misra","year":"2010","unstructured":"Misra, N., Philip, G., Raman, V., Saurabh, S.: The effect of girth on the kernelization complexity of Connected Dominating Set. In: Lodaya, K., Mahajan, M. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS2010, Chennai, India, December 15\u201318, 2010. Leibniz International Proceedings in Informatics (LIPIcs), vol. 8, pp. 96\u2013107. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Dagstuhl (2010)"},{"key":"9681_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/978-3-642-02927-1_59","volume-title":"Automata, Languages and Programming, 36th International Colloquium, ICALP2009, Proceedings, Part\u00a0I","author":"J. Nederlof","year":"2009","unstructured":"Nederlof, J.: Fast polynomial-space algorithms using M\u00f6bius inversion: improving on Steiner tree and related problems. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S.E., Thomas, W. (eds.) Automata, Languages and Programming, 36th International Colloquium, ICALP2009, Proceedings, Part\u00a0I, Rhodes, Greece, July 5\u201312, 2009. Lecture Notes in Computer Science, vol. 5555, pp. 713\u2013725. Springer, Berlin (2009)"},{"key":"9681_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1007\/978-3-642-04128-0_62","volume-title":"Algorithms\u2014ESA 2009, 17th Annual European Symposium, Proceedings","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.) Algorithms\u2014ESA 2009, 17th Annual European Symposium, Proceedings, Copenhagen, Denmark, September 7\u20139, 2009. Lecture Notes in Computer Science, vol. 5757, pp. 694\u2013705. Springer, Berlin (2009)"},{"issue":"2","key":"9681_CR29","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s00453-007-9148-9","volume":"52","author":"V. Raman","year":"2008","unstructured":"Raman, V., Saurabh, S.: Short cycles make W-hard problems hard: FPT algorithms for W-hard problems in graphs with no short cycles. Algorithmica 52(2), 203\u2013225 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"9681_CR30","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0095-8956(90)90121-F","volume":"48","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. VIII. A Kuratowski theorem for general surfaces. J.\u00a0Comb. Theory, Ser. B 48(2), 255\u2013288 (1990)","journal-title":"J.\u00a0Comb. Theory, Ser. B"},{"issue":"2","key":"9681_CR31","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","volume":"92","author":"N. Robertson","year":"2004","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner\u2019s conjecture. J. Comb. Theory, Ser. B 92(2), 325\u2013357 (2004)","journal-title":"J. Comb. Theory, Ser. B"},{"issue":"2","key":"9681_CR32","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1006\/jctb.1997.1761","volume":"70","author":"C. Thomassen","year":"1997","unstructured":"Thomassen, C.: A simpler proof of the excluded minor theorem for higher surfaces. J. Comb. Theory, Ser. B 70(2), 306\u2013311 (1997)","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9681-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9681-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9681-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:10Z","timestamp":1559123110000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9681-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,8,23]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9681"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9681-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,8,23]]}}}