{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:34Z","timestamp":1777596154350,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642348617","type":"print"},{"value":"9783642348624","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34862-4_9","type":"book-chapter","created":{"date-parts":[[2012,11,26]],"date-time":"2012-11-26T09:00:11Z","timestamp":1353920411000},"page":"120-133","source":"Crossref","is-referenced-by-count":11,"title":["Constant Thresholds Can Make Target Set Selection Tractable"],"prefix":"10.1007","author":[{"given":"Morgan","family":"Chopin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e9","family":"Nichterlein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Niedermeier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathias","family":"Weller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"5-6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1017\/S0963548310000271","volume":"19","author":"J. Balogh","year":"2010","unstructured":"Balogh, J., Bollob\u00e1s, B., Morris, R.: Bootstrap percolation in high dimensions. Combinatorics, Probability & Computing\u00a019(5-6), 643\u2013692 (2010)","journal-title":"Combinatorics, Probability & Computing"},{"issue":"1","key":"9_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/j.disopt.2010.09.007","volume":"8","author":"O. Ben-Zwi","year":"2011","unstructured":"Ben-Zwi, O., Hermelin, D., Lokshtanov, D., Newman, I.: Treewidth governs the complexity of target set selection. Discrete Optimization\u00a08(1), 87\u201396 (2011)","journal-title":"Discrete Optimization"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11269-0_2","volume-title":"Parameterized and Exact Computation","author":"H.L. Bodlaender","year":"2009","unstructured":"Bodlaender, H.L.: Kernelization: New Upper and Lower Bound Techniques. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 17\u201337. Springer, Heidelberg (2009)"},{"issue":"29","key":"9_CR4","doi-asserted-by":"publisher","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","volume":"412","author":"C.C. Centeno","year":"2011","unstructured":"Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theoretical Computer Science\u00a0412(29), 3693\u20133700 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1400","DOI":"10.1137\/08073617X","volume":"23","author":"N. Chen","year":"2009","unstructured":"Chen, N.: On the approximability of influence in social networks. SIAM Journal on Discrete Mathematics\u00a023(3), 1400\u20131415 (2009)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Chiang, C.-Y., Huang, L.-H., Li, B.-J., Wu, J., Yeh, H.-G.: Some results on the target set selection problem. Journal of Combinatorial Optimization (2012)","DOI":"10.1007\/s10878-012-9518-3"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Diestel, R.: Graph Theory, 4th edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer (2010)","DOI":"10.1007\/978-3-642-14279-6"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-642-32589-2_32","volume-title":"Mathematical Foundations of Computer Science 2012","author":"M. Doucha","year":"2012","unstructured":"Doucha, M., Kratochv\u00edl, J.: Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 348\u2013359. Springer, Heidelberg (2012)"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"9_CR10","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","volume":"157","author":"P.A. Dreyer Jr.","year":"2009","unstructured":"Dreyer Jr., P.A., Roberts, F.S.: Irreversible k-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discrete Applied Mathematics\u00a0157, 1615\u20131627 (2009)","journal-title":"Discrete Applied Mathematics"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Easley, D., Kleinberg, J.: Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press (2010)","DOI":"10.1017\/CBO9780511761942"},{"key":"9_CR12","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer (2006)"},{"issue":"1","key":"9_CR13","doi-asserted-by":"publisher","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. ACM SIGACT News\u00a038(1), 31\u201345 (2007)","journal-title":"ACM SIGACT News"},{"issue":"6","key":"9_CR14","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1017\/S0963548399004034","volume":"8","author":"J. Harant","year":"1999","unstructured":"Harant, J., Pruchnewski, A., Voigt, M.: On dominating sets and independent sets of graphs. Combinatorics, Probability and Computing\u00a08(6), 547\u2013553 (1999)","journal-title":"Combinatorics, Probability and Computing"},{"issue":"1","key":"9_CR15","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00224-008-9150-x","volume":"47","author":"F. H\u00fcffner","year":"2010","unstructured":"H\u00fcffner, F., Komusiewicz, C., Moser, H., Niedermeier, R.: Fixed-parameter algorithms for cluster vertex deletion. Theory of Computing Systems\u00a047(1), 196\u2013217 (2010)","journal-title":"Theory of Computing Systems"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proc. 9th ACM KDD, pp. 137\u2013146. ACM Press (2003)","DOI":"10.1145\/956750.956769"},{"issue":"2","key":"9_CR18","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.ipl.2003.10.004","volume":"89","author":"R. Klasing","year":"2004","unstructured":"Klasing, R., Laforest, C.: Hardness results and approximation algorithms of k-tuple domination in graphs. Information Processing Letters\u00a089(2), 75\u201383 (2004)","journal-title":"Information Processing Letters"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-32589-2_2","volume-title":"Mathematical Foundations of Computer Science 2012","author":"C. Komusiewicz","year":"2012","unstructured":"Komusiewicz, C., Niedermeier, R.: New Races in Parameterized Algorithmics. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol.\u00a07464, pp. 19\u201330. Springer, Heidelberg (2012)"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"H.W. Lenstra","year":"1983","unstructured":"Lenstra, H.W.: Integer programming with a fixed number of variables. Mathematics of Operations Research\u00a08, 538\u2013548 (1983)","journal-title":"Mathematics of Operations Research"},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On tractable cases of target set selection. Social Network Analysis and Mining (2012)","DOI":"10.1007\/s13278-012-0067-7"},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press (2006)","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0304-3975(01)00055-X","volume":"282","author":"D. Peleg","year":"2002","unstructured":"Peleg, D.: Local majorities, coalitions and monopolies in graphs: a review. Theoretical Computer Science\u00a0282, 231\u2013257 (2002)","journal-title":"Theoretical Computer Science"},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-540-85097-7_11","volume-title":"Combinatorial Optimization and Applications","author":"V. Raman","year":"2008","unstructured":"Raman, V., Saurabh, S., Srihari, S.: Parameterized Algorithms for Generalized Domination. In: Yang, B., Du, D.-Z., Wang, C.A. (eds.) COCOA 2008. LNCS, vol.\u00a05165, pp. 116\u2013126. Springer, Heidelberg (2008)"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-11440-3_22","volume-title":"WALCOM: Algorithms and Computation","author":"T. Reddy","year":"2010","unstructured":"Reddy, T., Krishna, D., Rangan, C.: Variants of Spreading Messages. In: Rahman, M. S., Fujita, S. (eds.) WALCOM 2010. LNCS, vol.\u00a05942, pp. 240\u2013251. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Design and Analysis of Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34862-4_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T13:06:53Z","timestamp":1620133613000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34862-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642348617","9783642348624"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34862-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}