{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T08:10:45Z","timestamp":1772266245836,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T00:00:00Z","timestamp":1649635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["KAKENHI JP20H05793, JP20K19742"],"award-info":[{"award-number":["KAKENHI JP20H05793, JP20K19742"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["KAKENHI JP18H04091, JP18K11168, JP18K11169, JP20H05793"],"award-info":[{"award-number":["KAKENHI JP18H04091, JP18K11168, JP18K11169, JP20H05793"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p><jats:sc>Graph Burning<\/jats:sc> asks, given a graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G = (V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and an integer <jats:italic>k<\/jats:italic>, whether there exists <jats:inline-formula><jats:alternatives><jats:tex-math>$$(b_{0},\\dots ,b_{k-1}) \\in V^{k}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msub>\n                        <mml:mi>b<\/mml:mi>\n                        <mml:mn>0<\/mml:mn>\n                      <\/mml:msub>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mo>\u22ef<\/mml:mo>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:msub>\n                        <mml:mi>b<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mi>k<\/mml:mi>\n                          <mml:mo>-<\/mml:mo>\n                          <mml:mn>1<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msub>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2208<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>V<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that every vertex in <jats:italic>G<\/jats:italic> has distance at most <jats:italic>i<\/jats:italic> from some <jats:inline-formula><jats:alternatives><jats:tex-math>$$b_{i}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msub>\n                    <mml:mi>b<\/mml:mi>\n                    <mml:mi>i<\/mml:mi>\n                  <\/mml:msub>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This problem is known to be NP-complete even on connected caterpillars of maximum degree 3. We study the parameterized complexity of this problem and answer all questions by Kare and Reddy\u00a0[IWOCA 2019] about the parameterized complexity of the problem. We show that the problem is W[2]-complete parameterized by <jats:italic>k<\/jats:italic> and that it does not admit a polynomial kernel parameterized by vertex cover number unless <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm {NP} \\subseteq \\mathrm {coNP\/poly}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>NP<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mi>coNP<\/mml:mi>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>poly<\/mml:mi>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We also show that the problem is fixed-parameter tractable parameterized by clique-width plus the maximum diameter among all connected components. This implies the fixed-parameter tractability parameterized by modular-width, by treedepth, and by distance to cographs. Using a different technique, we show that parameterization by distance to split graphs is also tractable. We finally show that the problem parameterized by max leaf number is XP.<\/jats:p>","DOI":"10.1007\/s00453-022-00962-8","type":"journal-article","created":{"date-parts":[[2022,4,11]],"date-time":"2022-04-11T06:03:42Z","timestamp":1649657022000},"page":"2379-2393","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parameterized Complexity of Graph Burning"],"prefix":"10.1007","volume":"84","author":[{"given":"Yasuaki","family":"Kobayashi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0087-853X","authenticated-orcid":false,"given":"Yota","family":"Otachi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,11]]},"reference":[{"issue":"38","key":"962_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0166-218X(92)90121-P","volume":"37","author":"N Alon","year":"1992","unstructured":"Alon, N.: Transmitting in the $$n$$-dimensional cube. Discret. Appl. Math. 37(38), 9\u201311 (1992). https:\/\/doi.org\/10.1016\/0166-218X(92)90121-P","journal-title":"Discret. Appl. Math."},{"key":"962_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2017.07.016","volume":"232","author":"S Bessy","year":"2017","unstructured":"Bessy, S., Bonato, A., Janssen, J.C.M., Rautenbach, D., Roshanbin, E.: Burning a graph is hard. Discret. Appl. Math. 232, 73\u201387 (2017). https:\/\/doi.org\/10.1016\/j.dam.2017.07.016","journal-title":"Discret. Appl. Math."},{"key":"962_CR3","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.dam.2017.09.012","volume":"235","author":"S Bessy","year":"2018","unstructured":"Bessy, S., Bonato, A., Janssen, J.C.M., Rautenbach, D., Roshanbin, E.: Bounds on the burning number. Discret. Appl. Math. 235, 16\u201322 (2018). https:\/\/doi.org\/10.1016\/j.dam.2017.09.012","journal-title":"Discret. Appl. Math."},{"issue":"35","key":"962_CR4","doi-asserted-by":"publisher","first-page":"4570","DOI":"10.1016\/j.tcs.2011.04.039","volume":"412","author":"HL 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). https:\/\/doi.org\/10.1016\/j.tcs.2011.04.039","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"962_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.11575\/cdm.v16i1.71194","volume":"16","author":"A Bonato","year":"2021","unstructured":"Bonato, A.: A survey of graph burning. Contributions Discret. Math. 16(1), 185\u2013197 (2021). https:\/\/doi.org\/10.11575\/cdm.v16i1.71194","journal-title":"Contributions Discret. Math."},{"issue":"6","key":"962_CR6","doi-asserted-by":"publisher","first-page":"2761","DOI":"10.1007\/s00373-021-02390-x","volume":"37","author":"A Bonato","year":"2021","unstructured":"Bonato, A., English, S., Kay, B., Moghbel, D.: Improved bounds for burning fence graphs. Graphs Comb. 37(6), 2761\u20132773 (2021). https:\/\/doi.org\/10.1007\/s00373-021-02390-x","journal-title":"Graphs Comb."},{"key":"962_CR7","doi-asserted-by":"publisher","first-page":"1311","DOI":"10.1007\/s00373-020-02182-9","volume":"36","author":"A Bonato","year":"2020","unstructured":"Bonato, A., Gunderson, K., Shaw, A.: Burning the plane. Graphs Comb. 36, 1311\u20131335 (2020). https:\/\/doi.org\/10.1007\/s00373-020-02182-9","journal-title":"Graphs Comb."},{"key":"962_CR8","doi-asserted-by":"publisher","unstructured":"Bonato, A., Janssen, J.C.M., Roshanbin, E.: Burning a graph as a model of social contagion. In: WAW 2014, vol 8882 of Lecture Notes in Computer Science, pp. 13\u201322, (2014). https:\/\/doi.org\/10.1007\/978-3-319-13123-8_2","DOI":"10.1007\/978-3-319-13123-8_2"},{"issue":"1\u20132","key":"962_CR9","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1080\/15427951.2015.1103339","volume":"12","author":"A Bonato","year":"2016","unstructured":"Bonato, A., Janssen, J.C.M., Roshanbin, E.: How to burn a graph. Internet Math. 12(1\u20132), 85\u2013100 (2016). https:\/\/doi.org\/10.1080\/15427951.2015.1103339","journal-title":"Internet Math."},{"key":"962_CR10","doi-asserted-by":"publisher","unstructured":"Bonato, A., Kamali, S.: Approximation algorithms for graph burning. In: TAMC 2019, volume 11436 of Lecture Notes in Computer Science, pp. 74\u201392, (2019). https:\/\/doi.org\/10.1007\/978-3-030-14812-6_6","DOI":"10.1007\/978-3-030-14812-6_6"},{"key":"962_CR11","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/j.tcs.2018.05.035","volume":"794","author":"A Bonato","year":"2019","unstructured":"Bonato, A., Lidbetter, T.: Bounds on the burning numbers of spiders and path-forests. Theor. Comput. Sci. 794, 12\u201319 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2018.05.035","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"962_CR12","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"DG Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput. 34(4), 825\u2013847 (2005). https:\/\/doi.org\/10.1137\/S0097539701385351","journal-title":"SIAM J. Comput."},{"issue":"2","key":"962_CR13","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. 33(2), 125\u2013150 (2000). https:\/\/doi.org\/10.1007\/s002249910009","journal-title":"Theory Comput. Syst."},{"key":"962_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F.V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"962_CR15","doi-asserted-by":"publisher","unstructured":"Das, S., Dev, S.R., Sadhukhan, A., Sahoo, U.K., Sen, S.: Burning spiders. In: CALDAM 2018, volume 10743 of Lecture Notes in Computer Science, pp. 155\u2013163, (2018). https:\/\/doi.org\/10.1007\/978-3-319-74180-2_13","DOI":"10.1007\/978-3-319-74180-2_13"},{"issue":"2","key":"962_CR16","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2650261","volume":"11","author":"M Dom","year":"2014","unstructured":"Dom, M., Lokshtanov, D., Saurabh, S.: Kernelization lower bounds through colors and IDs. ACM Trans. Algorithms 11(2), 13:1-13:20 (2014). https:\/\/doi.org\/10.1145\/2650261","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"962_CR17","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"RG Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness I: basic results. SIAM J. Comput. 24(4), 873\u2013921 (1995). https:\/\/doi.org\/10.1137\/S0097539792228228","journal-title":"SIAM J. Comput."},{"key":"962_CR18","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0515-9","DOI":"10.1007\/978-1-4612-0515-9"},{"issue":"1","key":"962_CR19","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"MR Fellows","year":"1992","unstructured":"Fellows, M.R., Langston, M.A.: On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Discret. Math. 5(1), 117\u2013126 (1992). https:\/\/doi.org\/10.1137\/0405010","journal-title":"SIAM J. Discret. Math."},{"key":"962_CR20","unstructured":"Fitzpatrick, S.L., Wilm, L.: Burning circulant graphs. CoRR, (2017). arXiv:1706.03106"},{"key":"962_CR21","unstructured":"Foldes, S., Hammer, P.L.: Split graphs. In: the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing, volume\u00a019 of Congressus Numerantium, pp. 311\u2013315 (1977)"},{"key":"962_CR22","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: WG 2004, volume 3353 of Lecture Notes in Computer Science, pp. 245\u2013256, (2004) https:\/\/doi.org\/10.1007\/978-3-540-30559-0_21","DOI":"10.1007\/978-3-540-30559-0_21"},{"key":"962_CR23","doi-asserted-by":"publisher","unstructured":"Gajarsk\u00fd J., Lampis, M., Ordyniak, S.: Parameterized algorithms for modular-width. In: IPEC 2013, volume 8246 of Lecture Notes in Computer Science, pp. 163\u2013176, (2013). https:\/\/doi.org\/10.1007\/978-3-319-03898-8_15","DOI":"10.1007\/978-3-319-03898-8_15"},{"key":"962_CR24","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"3","key":"962_CR25","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/3051095","volume":"64","author":"M Grohe","year":"2017","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. J. ACM 64(3), 17:1-17:32 (2017). https:\/\/doi.org\/10.1145\/3051095","journal-title":"J. ACM"},{"issue":"2","key":"962_CR26","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/s00224-016-9685-1","volume":"60","author":"F Gurski","year":"2017","unstructured":"Gurski, F.: The behavior of clique-width under graph operations and graph transformations. Theory Comput. Syst. 60(2), 346\u2013376 (2017). https:\/\/doi.org\/10.1007\/s00224-016-9685-1","journal-title":"Theory Comput. Syst."},{"key":"962_CR27","doi-asserted-by":"publisher","unstructured":"Hiller, M., Triesch, E., Koster, A.M.C.A.: On the burning number of $$p$$-caterpillars. In: CTW 2020, volume\u00a05 of AIRO Springer Series, pp. 145\u2013156, (2020). https:\/\/doi.org\/10.1007\/978-3-030-63072-0_12","DOI":"10.1007\/978-3-030-63072-0_12"},{"key":"962_CR28","doi-asserted-by":"publisher","unstructured":"Ho, T.-Y., Hsu, L.-H., Sung, T.-Y.: Transmitting on various network topologies. Networks 27(2), 145\u2013157 (1996). https:\/\/doi.org\/10.1002\/(SICI)1097-0037(199603)27:2<145::AID-NET6>3.0.CO;2-K","DOI":"10.1002\/(SICI)1097-0037(199603)27:2<145::AID-NET6>3.0.CO;2-K"},{"key":"962_CR29","doi-asserted-by":"publisher","unstructured":"Janssen, R.: The burning number of directed graphs: Bounds and computational complexity. Theory Appl. Graphs 7(1), Article 8, (2020). https:\/\/doi.org\/10.20429\/tag.2020.070108","DOI":"10.20429\/tag.2020.070108"},{"issue":"5","key":"962_CR30","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0020-0190(94)00105-7","volume":"51","author":"J-S Jwo","year":"1994","unstructured":"Jwo, J.-S., Tuan, T.-C.: On transmitting delay in a distance-transitive strongly antipodal graph. Inf. Process. Lett. 51(5), 233\u2013235 (1994). https:\/\/doi.org\/10.1016\/0020-0190(94)00105-7","journal-title":"Inf. Process. Lett."},{"key":"962_CR31","doi-asserted-by":"publisher","unstructured":"Kamali, S., Miller, A., Zhang, K: Burning two worlds. In: SOFSEM 2020, volume 12011, pp. 113\u2013124. Springer, (2020). https:\/\/doi.org\/10.1007\/978-3-030-38919-2_10","DOI":"10.1007\/978-3-030-38919-2_10"},{"key":"962_CR32","doi-asserted-by":"publisher","unstructured":"Kare, A.S., Vinod Reddy, I.: Parameterized algorithms for graph burning problem. In: IWOCA 2019, volume 11638 of Lecture Notes in Computer Science, pp. 304\u2013314, (2019). https:\/\/doi.org\/10.1007\/978-3-030-25005-8_25","DOI":"10.1007\/978-3-030-25005-8_25"},{"issue":"1","key":"962_CR33","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/0404010","volume":"4","author":"DJ Kleitman","year":"1991","unstructured":"Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discret. Math. 4(1), 99\u2013106 (1991). https:\/\/doi.org\/10.1137\/0404010","journal-title":"SIAM J. Discret. Math."},{"key":"962_CR34","doi-asserted-by":"publisher","unstructured":"Land, M.R., Lu, L.: An upper bound on the burning number of graphs. In: WAW 2016, volume 10088 of Lecture Notes in Computer Science. pp. 1\u20138, (2016). https:\/\/doi.org\/10.1007\/978-3-319-49787-7_1","DOI":"10.1007\/978-3-319-49787-7_1"},{"key":"962_CR35","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1016\/j.dam.2020.03.062","volume":"284","author":"H Liu","year":"2020","unstructured":"Liu, H., Hu, X., Hu, X.: Burning number of caterpillars. Discret. Appl. Math. 284, 332\u2013340 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.03.062","journal-title":"Discret. Appl. Math."},{"key":"962_CR36","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1007\/s40840-020-00969-w","volume":"44","author":"H Liu","year":"2021","unstructured":"Liu, H., Hu, X., Hu, X.: Burning numbers of path forests and spiders. Bull. Malays. Math. Sci. Soc. 44, 661\u2013681 (2021). https:\/\/doi.org\/10.1007\/s40840-020-00969-w","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"962_CR37","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1016\/j.amc.2019.05.031","volume":"361","author":"H Liu","year":"2019","unstructured":"Liu, H., Zhang, R., Hu, X.: Burning number of theta graphs. Appl. Math. Comput. 361, 246\u2013257 (2019). https:\/\/doi.org\/10.1016\/j.amc.2019.05.031","journal-title":"Appl. Math. Comput."},{"issue":"9","key":"962_CR38","doi-asserted-by":"publisher","first-page":"1056","DOI":"10.1109\/12.537129","volume":"45","author":"Z Liu","year":"1996","unstructured":"Liu, Z., Sung, T.-Y.: Routing and transmitting problems in de Bruijn networks. IEEE Trans. Comput. 45(9), 1056\u20131062 (1996). https:\/\/doi.org\/10.1109\/12.537129","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"962_CR39","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s00373-017-1768-5","volume":"33","author":"D Mitsche","year":"2017","unstructured":"Mitsche, D., Pralat, P., Roshanbin, E.: Burning graphs: a probabilistic perspective. Graphs Comb. 33(2), 449\u2013471 (2017). https:\/\/doi.org\/10.1007\/s00373-017-1768-5","journal-title":"Graphs Comb."},{"key":"962_CR40","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/j.tcs.2018.06.036","volume":"746","author":"Dieter Mitsche","year":"2018","unstructured":"Mitsche, Dieter, Pralat, Pawel, Roshanbin, Elham: Burning number of graph products. Theor. Comput. Sci. 746, 124\u2013135 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.06.036","journal-title":"Theor. Comput. Sci."},{"key":"962_CR41","doi-asserted-by":"publisher","unstructured":"Mondal, D., Parthiban, N., Kavitha, V., Rajasingh, I.: APX-hardness and approximation for the $$k$$-burning number problem. In: WALCOM 2021, volume 12635 of Lecture Notes in Computer Science. pp. 272\u2013283, (2021). https:\/\/doi.org\/10.1007\/978-3-030-68211-8_22","DOI":"10.1007\/978-3-030-68211-8_22"},{"key":"962_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Algorithms and Combinatorics. Springer, Berlin (2012). https:\/\/doi.org\/10.1007\/978-3-642-27875-4"},{"issue":"1","key":"962_CR43","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1145\/1435375.1435385","volume":"5","author":"S-I Oum","year":"2008","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Trans. Algorithms 5(1), 101\u20131020 (2008). https:\/\/doi.org\/10.1145\/1435375.1435385","journal-title":"ACM Trans. Algorithms"},{"key":"962_CR44","unstructured":"Sorge, M., Weller, M.: The graph parameter hierarchy, 2019. URL: https:\/\/manyu.pro\/assets\/parameter-hierarchy.pdf"},{"key":"962_CR45","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2020.125447","author":"TS Tan","year":"2020","unstructured":"Tan, T.S., Teh, W.C.: Graph burning: tight bounds on the burning numbers of path forests and spiders. Appl. Math. Comput. (2020). https:\/\/doi.org\/10.1016\/j.amc.2020.125447","journal-title":"Appl. Math. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00962-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00962-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00962-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:10:47Z","timestamp":1658409047000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00962-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,11]]},"references-count":45,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["962"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00962-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,11]]},"assertion":[{"value":"8 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 April 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}