{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:29Z","timestamp":1759638149849},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_4","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T13:53:05Z","timestamp":1271857985000},"page":"26-37","source":"Crossref","is-referenced-by-count":8,"title":["Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set"],"prefix":"10.1007","author":[{"given":"Qianping","family":"Gu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Navid","family":"Imani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"4_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.R., Niedermeier, R.: Polynomial-time data reduction for dominating set. Journal of the ACM\u00a051(3), 363\u2013384 (2004) (electronic)","journal-title":"Journal of the ACM"},{"key":"4_CR2","first-page":"238","volume-title":"Correlation clustering","author":"N. Bansal","year":"2002","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering, p. 238. IEEE Computer Society, Los Alamitos (2002)"},{"key":"4_CR3","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/0-387-23830-1_8","volume-title":"Handbook of combinatorial optimization","author":"J. Blum","year":"2005","unstructured":"Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and MANETs. In: Handbook of combinatorial optimization, vol.\u00a0B (Suppl.), pp. 329\u2013369. Springer, New York (2005)"},{"key":"4_CR4","unstructured":"Bodlaender, H.L., Fomin, F.V., Lokshtanov, D., Penninkx, E., Saurabh, S., Thilikos, D.M.: (Meta) Kernelization, April 4 (2009), \n                  \n                    http:\/\/arxiv.org\/abs\/0904.0727"},{"issue":"3","key":"4_CR5","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/0222038","volume":"22","author":"J.F. Buss","year":"1993","unstructured":"Buss, J.F., Goldsmith, J.: Nondeterminism within P. SIAM Journal on Computing\u00a022(3), 560\u2013572 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/S0168-0072(95)00020-8","volume":"84","author":"L. Cai","year":"1997","unstructured":"Cai, L., Chen, J., Downey, R.G., Fellows, M.R.: Advice classes of parameterized tractability. Annals of Pure and Applied Logic\u00a084(1), 119\u2013138 (1997)","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"4_CR7","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1137\/050646354","volume":"37","author":"J. Chen","year":"2007","unstructured":"Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: Lower bounds and upper bounds on kernel size. SIAM Journal on Computing\u00a037(4), 1077\u20131106 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-45995-2_32","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Chen","year":"2002","unstructured":"Chen, J., Kanj, I.: Improved exact algorithms for MAX-SAT. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 341\u2013355. Springer, Heidelberg (2002)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/11841036_27","volume-title":"Algorithms \u2013 ESA 2006","author":"F. Dorn","year":"2006","unstructured":"Dorn, F.: Dynamic programming and fast matrix multiplication. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 280\u2013291. Springer, Heidelberg (2006)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/11561071_11","volume-title":"Algorithms \u2013 ESA 2005","author":"F. Dorn","year":"2005","unstructured":"Dorn, F., Penninkx, E., Bodlaender, H.L., Fomin, F.V.: Efficient exact algorithms on planar graphs: Exploiting sphere cut branch decompositions. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 95\u2013106. Springer, Heidelberg (2005)"},{"key":"4_CR11","series-title":"Monographs in Computer Science","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. Monographs in Computer Science. Springer, New York (1999)"},{"key":"4_CR12","unstructured":"Gu, Q., Imani, N.: Small Kernel for Planar Connected Sominating Set. TR 2009-12, School of Computing Science, Simon Fraser University, Burnaby, BC, Canada (June 2009), \n                  \n                    ftp:\/\/fas.sfu.ca\/pub\/cs\/TR\/2009\/CMPT2009-12.pdf"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-540-73420-8_34","volume-title":"Automata, Languages and Programming","author":"J. Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Linear Problem Kernels for NP-Hard Problems on Planar Graphs. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 375\u2013386. Springer, Heidelberg (2007)"},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"6-7","key":"4_CR15","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1016\/j.dam.2005.09.020","volume":"155","author":"J. Gramm","year":"2007","unstructured":"Gramm, J., Nierhoff, T., Sharan, R., Tantau, T.: Haplotyping with missing data via perfect path phylogenies. Discrete Applied Mathematics\u00a0155(6-7), 788\u2013805 (2007)","journal-title":"Discrete Applied Mathematics"},{"issue":"3","key":"4_CR16","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/net.20081","volume":"46","author":"J. Guo","year":"2005","unstructured":"Guo, J., Niedermeier, R.: Fixed-parameter tractability and data reduction for multicut in trees. Networks\u00a046(3), 124\u2013135 (2005)","journal-title":"Networks"},{"key":"4_CR17","series-title":"Monographs and Textbooks in Pure and Applied Mathematics","volume-title":"Fundamentals of Domination in Graphs","author":"T.W. Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol.\u00a0208. Marcel Dekker, New York (1998)"},{"key":"4_CR18","unstructured":"Imani, N.: Data Reduction for Connected Dominating Set. Master Thesis, Simon Fraser University, BC, Canada (August 2008)"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Mnich, M., Saurabh, S.: Linear kernel for planar connected dominating set. To appear in Proceedings of TAMC (May 2009)","DOI":"10.1007\/978-3-642-02017-9_31"},{"issue":"2","key":"4_CR20","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSat and MaxCut. Journal of Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"Journal of Algorithms"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1007\/BF01580444","volume":"8","author":"G.L. Nemhauser","year":"1975","unstructured":"Nemhauser, G.L., Trotter Jr., L.E.: Vertex packings: structural properties and algorithms. Mathematical Programming\u00a08, 232\u2013248 (1975)","journal-title":"Mathematical Programming"},{"key":"4_CR22","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R. Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications, vol.\u00a031. Oxford University Press, Oxford (2006)"},{"key":"4_CR23","unstructured":"Weihe, K.: Covering trains by stations or the power of data reduction. In: Proceedings of Algorithms and Experiments, ALEX, pp. 1\u20138 (1998)"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44691-5_1","volume-title":"Algorithm Engineering","author":"K. Weihe","year":"2000","unstructured":"Weihe, K.: On the differences between \u201cpractical\u201d and \u201capplied\u201d. In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol.\u00a01982, pp. 1\u201310. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,30]],"date-time":"2021-04-30T12:05:37Z","timestamp":1619784337000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}