{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:58Z","timestamp":1740109318037,"version":"3.37.3"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T00:00:00Z","timestamp":1663113600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["16-11-10123"],"award-info":[{"award-number":["16-11-10123"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,2]]},"DOI":"10.1007\/s00453-022-01031-w","type":"journal-article","created":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T13:04:40Z","timestamp":1663160680000},"page":"384-405","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Solving Target Set Selection with Bounded Thresholds Faster than $$2^n$$"],"prefix":"10.1007","volume":"85","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2291-2556","authenticated-orcid":false,"given":"Ivan","family":"Bliznets","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3327-9768","authenticated-orcid":false,"given":"Danil","family":"Sagunov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,14]]},"reference":[{"issue":"3","key":"1031_CR1","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0168-0072(94)00034-z","volume":"73","author":"KA Abrahamson","year":"1995","unstructured":"Abrahamson, K.A., Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analogues. Ann. Pure Appl. Logic 73(3), 235\u2013276 (1995). https:\/\/doi.org\/10.1016\/0168-0072(94)00034-z","journal-title":"Ann. Pure Appl. Logic"},{"issue":"44\u201346","key":"1031_CR2","doi-asserted-by":"publisher","first-page":"4017","DOI":"10.1016\/j.tcs.2010.08.021","volume":"411","author":"E Ackerman","year":"2010","unstructured":"Ackerman, E., Ben-Zwi, O., Wolfovitz, G.: Combinatorial model and bounds for target set selection. Theoret. Comput. Sci. 411(44\u201346), 4017\u20134022 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2010.08.021","journal-title":"Theoret. Comput. Sci."},{"key":"1031_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.endm.2013.10.017","volume":"44","author":"R Ara\u00fajo","year":"2013","unstructured":"Ara\u00fajo, R., Sampaio, R., Szwarcfiter, J.: The convexity of induced paths of order three. Electron. Notes Discrete Math. 44, 109\u2013114 (2013). https:\/\/doi.org\/10.1016\/j.endm.2013.10.017","journal-title":"Electron. Notes Discrete Math."},{"key":"1031_CR4","volume-title":"Information Theory. Dover Books on Mathematics","author":"R Ash","year":"1990","unstructured":"Ash, R.: Information Theory. Dover Books on Mathematics. Dover Publications, Mineola, NY (1990)"},{"issue":"5\u20136","key":"1031_CR5","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. Comb. Probab. Comput. 19(5\u20136), 643\u2013692 (2010)","journal-title":"Comb. Probab. Comput."},{"key":"1031_CR6","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.jda.2014.05.001","volume":"27","author":"C Bazgan","year":"2014","unstructured":"Bazgan, C., Chopin, M., Nichterlein, A., Sikora, F.: Parameterized approximability of maximizing the spread of influence in networks. J. Discret. Algorithms 27, 54\u201365 (2014). https:\/\/doi.org\/10.1016\/j.jda.2014.05.001","journal-title":"J. Discret. Algorithms"},{"issue":"1","key":"1031_CR7","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. Discret. Optim. 8(1), 87\u201396 (2011). https:\/\/doi.org\/10.1016\/j.disopt.2010.09.007","journal-title":"Discret. Optim."},{"issue":"3","key":"1031_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.jda.2011.03.002","volume":"9","author":"D Binkele-Raible","year":"2011","unstructured":"Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the $$2^n$$-barrier for Irredundance: Two lines of attack. J. Discret. Algorithms 9(3), 214\u2013230 (2011). https:\/\/doi.org\/10.1016\/j.jda.2011.03.002","journal-title":"J. Discret. Algorithms"},{"issue":"2","key":"1031_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2151171.2151181","volume":"8","author":"A Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: The traveling salesman problem in bounded degree graphs. ACM Trans. Algorithms 8(2), 1\u201313 (2012). https:\/\/doi.org\/10.1145\/2151171.2151181","journal-title":"ACM Trans. Algorithms"},{"key":"1031_CR10","doi-asserted-by":"publisher","unstructured":"Bliznets, I., Fomin, F.V., Pilipczuk, M., Villanger, Y.: Largest Chordal and Interval Subgraphs Faster Than $$2^n$$. In: Lecture Notes in Computer Science, pp. 193\u2013204. Springer Berlin Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_17","DOI":"10.1007\/978-3-642-40450-4_17"},{"issue":"29","key":"1031_CR11","doi-asserted-by":"publisher","first-page":"3693","DOI":"10.1016\/j.tcs.2011.03.029","volume":"412","author":"CC Centeno","year":"2011","unstructured":"Centeno, C.C., Dourado, M.C., Penso, L.D., Rautenbach, D., Szwarcfiter, J.L.: Irreversible conversion of graphs. Theoret. Comput. Sci. 412(29), 3693\u20133700 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2011.03.029","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1031_CR12","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 J. Discret. Math. 23(3), 1400\u20131415 (2009). https:\/\/doi.org\/10.1137\/08073617x","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1031_CR13","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s00224-013-9499-3","volume":"55","author":"M Chopin","year":"2013","unstructured":"Chopin, M., Nichterlein, A., Niedermeier, R., Weller, M.: Constant Thresholds Can Make Target Set Selection Tractable. Theor. Comput. Syst. 55(1), 61\u201383 (2013). https:\/\/doi.org\/10.1007\/s00224-013-9499-3","journal-title":"Theor. Comput. Syst."},{"issue":"3","key":"1031_CR14","doi-asserted-by":"publisher","first-page":"692","DOI":"10.1007\/s00453-012-9694-7","volume":"68","author":"M Cygan","year":"2012","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Scheduling Partially Ordered Jobs Faster than $$2^n$$. Algorithmica 68(3), 692\u2013714 (2012). https:\/\/doi.org\/10.1007\/s00453-012-9694-7","journal-title":"Algorithmica"},{"issue":"2","key":"1031_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s00453-013-9796-x","volume":"70","author":"M Cygan","year":"2013","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M., Wojtaszczyk, J.O.: Solving the 2-Disjoint Connected Subgraphs Problem Faster than $$2^n$$. Algorithmica 70(2), 195\u2013207 (2013). https:\/\/doi.org\/10.1007\/s00453-013-9796-x","journal-title":"Algorithmica"},{"key":"1031_CR16","doi-asserted-by":"publisher","unstructured":"Cygan, M., Pilipczuk, M., Wojtaszczyk, J.O.: Capacitated Domination Faster Than $$O(2^n)$$. In: Lecture Notes in Computer Science, pp. 74\u201380. Springer Berlin Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13731-0_8","DOI":"10.1007\/978-3-642-13731-0_8"},{"issue":"7","key":"1031_CR17","doi-asserted-by":"publisher","first-page":"1615","DOI":"10.1016\/j.dam.2008.09.012","volume":"157","author":"PA Dreyer Jr","year":"2009","unstructured":"Dreyer, P.A., Jr., Roberts, F.S.: Irreversible $$k$$-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion. Discret. Appl. Math. 157(7), 1615\u20131627 (2009)","journal-title":"Discret. Appl. Math."},{"key":"1031_CR18","unstructured":"Dvo\u0159\u00e1k, P., Knop, D., Toufar, T.: Target Set Selection in Dense Graph Classes. arXiv preprint arXiv:1610.07530 (2016)"},{"issue":"2","key":"1031_CR19","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"FV Fomin","year":"2007","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms. Algorithmica 52(2), 293\u2013307 (2007). https:\/\/doi.org\/10.1007\/s00453-007-9152-0","journal-title":"Algorithmica"},{"issue":"2","key":"1031_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/s00453-007-9145-z","volume":"52","author":"FV Fomin","year":"2007","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Solving Connected Dominating Set Faster than $$2^n$$. Algorithmica 52(2), 153\u2013166 (2007). https:\/\/doi.org\/10.1007\/s00453-007-9145-z","journal-title":"Algorithmica"},{"issue":"1","key":"1031_CR21","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/s00453-012-9731-6","volume":"69","author":"FV Fomin","year":"2012","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D., Papadopoulos, C., Villanger, Y.: Enumerating Minimal Subset Feedback Vertex Sets. Algorithmica 69(1), 216\u2013231 (2012). https:\/\/doi.org\/10.1007\/s00453-012-9731-6","journal-title":"Algorithmica"},{"key":"1031_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms, 1st edn. Springer-Verlag, Berlin, Heidelberg (2010)","edition":"1"},{"key":"1031_CR23","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Exact Algorithm for the Maximum Induced Planar Subgraph Problem. In: Algorithms \u2013 ESA 2011, pp. 287\u2013298. Springer Berlin Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23719-5_25","DOI":"10.1007\/978-3-642-23719-5_25"},{"key":"1031_CR24","doi-asserted-by":"publisher","unstructured":"Hartmann, T.A.: Target Set Selection Parameterized by Clique-Width and Maximum Threshold. In: SOFSEM 2018: Theory and Practice of Computer Science, pp. 137\u2013149. Springer International Publishing (2017). 1https:\/\/doi.org\/10.1007\/978-3-319-73117-9_10","DOI":"10.1007\/978-3-319-73117-9_10"},{"key":"1031_CR25","doi-asserted-by":"publisher","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD \u201903. ACM Press (2003). https:\/\/doi.org\/10.1145\/956750.956769","DOI":"10.1145\/956750.956769"},{"issue":"3","key":"1031_CR26","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1016\/j.tcs.2005.10.007","volume":"351","author":"D Marx","year":"2006","unstructured":"Marx, D.: Parameterized graph separation problems. Theoret. Comput. Sci. 351(3), 394\u2013406 (2006). https:\/\/doi.org\/10.1016\/j.tcs.2005.10.007","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"1031_CR27","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s13278-012-0067-7","volume":"3","author":"A Nichterlein","year":"2012","unstructured":"Nichterlein, A., Niedermeier, R., Uhlmann, J., Weller, M.: On tractable cases of Target Set Selection. Soc. Netw. Anal. Min. 3(2), 233\u2013256 (2012). https:\/\/doi.org\/10.1007\/s13278-012-0067-7","journal-title":"Soc. Netw. Anal. Min."},{"issue":"2\u20133","key":"1031_CR28","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/s0166-218x(98)00043-2","volume":"86","author":"D Peleg","year":"1998","unstructured":"Peleg, D.: Size bounds for dynamic monopolies. Discret. Appl. Math. 86(2\u20133), 263\u2013273 (1998). https:\/\/doi.org\/10.1016\/s0166-218x(98)00043-2","journal-title":"Discret. Appl. Math."},{"key":"1031_CR29","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M.: Exact Algorithms for Induced Subgraph Problems. In: Encyclopedia of Algorithms, pp. 1\u20135. Springer US (2015). https:\/\/doi.org\/10.1007\/978-3-642-27848-8_520-1","DOI":"10.1007\/978-3-642-27848-8_520-1"},{"key":"1031_CR30","doi-asserted-by":"publisher","unstructured":"Pilipczuk, M., Pilipczuk, M.: Finding a Maximum Induced Degenerate Subgraph Faster Than $$2^n$$. In: Parameterized and Exact Computation, pp. 3\u201312. Springer Berlin Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33293-7_3","DOI":"10.1007\/978-3-642-33293-7_3"},{"key":"1031_CR31","doi-asserted-by":"crossref","unstructured":"Razgon, I.: Computing Minimum Directed Feedback Vertex Set in $$O^*(1.9977^n)$$. In: Theoretical Computer Science, pp. 70\u201381. World Scientific (2007)","DOI":"10.1142\/9789812770998_0010"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01031-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01031-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01031-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,27]],"date-time":"2023-01-27T09:18:07Z","timestamp":1674811087000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01031-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,14]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,2]]}},"alternative-id":["1031"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01031-w","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,9,14]]},"assertion":[{"value":"14 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare no conflicts of interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}