{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:34:33Z","timestamp":1783578873878,"version":"3.55.0"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T00:00:00Z","timestamp":1590710400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T00:00:00Z","timestamp":1590710400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1618301"],"award-info":[{"award-number":["CCF-1618301"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1616248"],"award-info":[{"award-number":["CCF-1616248"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00453-020-00720-8","type":"journal-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T19:02:53Z","timestamp":1590778973000},"page":"2337-2359","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Parameterized Leaf Power Recognition via Embedding into Graph Products"],"prefix":"10.1007","volume":"82","author":[{"given":"David","family":"Eppstein","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0069-2863","authenticated-orcid":false,"given":"Elham","family":"Havvaei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,5,29]]},"reference":[{"issue":"4","key":"720_CR1","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1007\/s00453-008-9204-0","volume":"54","author":"N Alon","year":"2009","unstructured":"Alon, N., Gutner, S.: Linear time algorithms for finding a dominating set of fixed size in degenerated graphs. Algorithmica 54(4), 544 (2009)","journal-title":"Algorithmica"},{"issue":"2","key":"720_CR2","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S Arnborg","year":"1991","unstructured":"Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308\u2013340 (1991). https:\/\/doi.org\/10.1016\/0196-6774(91)90006-K","journal-title":"J. Algorithms"},{"key":"720_CR3","doi-asserted-by":"publisher","unstructured":"Bannach, M., Berndt, S.: Practical access to dynamic programming on tree decompositions. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms (ESA 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 112, pp. 6:1\u20136:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.6. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9469","DOI":"10.4230\/LIPIcs.ESA.2018.6"},{"key":"720_CR4","doi-asserted-by":"crossref","unstructured":"Bannister, M.J., Eppstein, D.: Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. In: International Symposium on Graph Drawing, pp. 210\u2013221. Springer (2014)","DOI":"10.1007\/978-3-662-45803-7_18"},{"key":"720_CR5","volume-title":"Nonserial Dynamic Programming","author":"U Bertel\u00e9","year":"1972","unstructured":"Bertel\u00e9, U., Brioschi, F.: Nonserial Dynamic Programming. Academic Press, London (1972)"},{"key":"720_CR6","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: International Colloquium on Automata, Languages, and Programming, pp. 105\u2013118. Springer (1988)","DOI":"10.1007\/3-540-19488-6_110"},{"issue":"1\u20132","key":"720_CR7","first-page":"1","volume":"11","author":"HL Bodlaender","year":"1993","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybern. 11(1\u20132), 1\u201321 (1993)","journal-title":"Acta Cybern."},{"key":"720_CR8","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Hundt, C.: Ptolemaic graphs and interval graphs are leaf powers. In: Latin American Symposium on Theoretical Informatics, pp. 479\u2013491. Springer (2008)","DOI":"10.1007\/978-3-540-78773-0_42"},{"issue":"4","key":"720_CR9","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1016\/j.disc.2009.10.006","volume":"310","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Hundt, C., Mancini, F., Wagner, P.: Rooted directed path graphs are leaf powers. Discrete Math. 310(4), 897\u2013910 (2010). https:\/\/doi.org\/10.1016\/j.disc.2009.10.006","journal-title":"Discrete Math."},{"issue":"4","key":"720_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.ipl.2006.01.004","volume":"98","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Le, V.B.: Structure and linear time recognition of 3-leaf powers. Inf. Process. Lett. 98(4), 133\u2013138 (2006). https:\/\/doi.org\/10.1016\/j.ipl.2006.01.004","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"720_CR11","doi-asserted-by":"publisher","first-page":"3843","DOI":"10.1016\/j.disc.2008.10.025","volume":"309","author":"A Brandst\u00e4dt","year":"2009","unstructured":"Brandst\u00e4dt, A., Le, V.B., Rautenbach, D.: A forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. Discrete Math. 309(12), 3843\u20133852 (2009). https:\/\/doi.org\/10.1016\/j.disc.2008.10.025","journal-title":"Discrete Math."},{"issue":"1","key":"720_CR12","doi-asserted-by":"publisher","first-page":"A11:1","DOI":"10.1145\/1435375.1435386","volume":"5","author":"A Brandst\u00e4dt","year":"2009","unstructured":"Brandst\u00e4dt, A., Le, V.B., Sritharan, R.: Structure and linear-time recognition of 4-leaf powers. ACM Trans. Algorithms 5(1), A11:1\u2013A11:22 (2009). https:\/\/doi.org\/10.1145\/1435375.1435386","journal-title":"ACM Trans. Algorithms"},{"key":"720_CR13","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Wagner, P.: On k-versus (k+ 1)-leaf powers. In: International Conference on Combinatorial Optimization and Applications, pp. 171\u2013179. Springer (2008)","DOI":"10.1007\/978-3-540-85097-7_16"},{"key":"720_CR14","doi-asserted-by":"crossref","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: a new method for solving fixed-cardinality optimization problems. In: International Workshop on Parameterized and Exact Computation, pp. 239\u2013250. Springer (2006)","DOI":"10.1007\/11847250_22"},{"key":"720_CR15","doi-asserted-by":"crossref","unstructured":"Chang, M.S., Ko, M.T.: The 3-Steiner root problem. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 109\u2013120. Springer (2007)","DOI":"10.1007\/978-3-540-74839-7_11"},{"issue":"2","key":"720_CR16","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-013-9815-y","volume":"71","author":"MS Chang","year":"2015","unstructured":"Chang, M.S., Ko, M.T., Lu, H.I.: Linear-time algorithms for tree root problems. Algorithmica 71(2), 471\u2013495 (2015)","journal-title":"Algorithmica"},{"issue":"4","key":"720_CR17","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539701389154","volume":"32","author":"ZZ Chen","year":"2003","unstructured":"Chen, Z.Z., Jiang, T., Lin, G.: Computing phylogenetic roots with bounded degrees and errors. SIAM J. Comput. 32(4), 864\u2013879 (2003). https:\/\/doi.org\/10.1137\/S0097539701389154","journal-title":"SIAM J. Comput."},{"issue":"1","key":"720_CR18","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B Courcelle","year":"1990","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990). https:\/\/doi.org\/10.1016\/0890-5401(90)90043-H","journal-title":"Inf. Comput."},{"key":"720_CR19","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: On the expression of graph properties in some fragments of monadic second-order logic. In: Immerman, N., Kolaitis, P.G. (eds.) Descriptive Complexity and Finite Models: Proceedings of a DIMACS Workshop, January 14\u201317, 1996, Princeton University, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a031, pp. 33\u201362. American Mathematical Society, Providence, RI (1997)","DOI":"10.1090\/dimacs\/031\/02"},{"key":"720_CR20","doi-asserted-by":"publisher","unstructured":"Courcelle, B.: The expression of graph properties and graph transformations in monadic second-order logic. In: Handbook of Graph Grammars and Computing by Graph Transformation, vol. 1, pp. 313\u2013400. World Scientific, River Edge, NJ (1997). https:\/\/doi.org\/10.1142\/9789812384720_0005","DOI":"10.1142\/9789812384720_0005"},{"issue":"2","key":"720_CR21","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. Comput. Syst. Sci. 46(2), 218\u2013270 (1993). https:\/\/doi.org\/10.1016\/0022-0000(93)90004-G","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"720_CR22","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":"720_CR23","doi-asserted-by":"crossref","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R.: Error compensation in leaf root problems. In: International Symposium on Algorithms and Computation, pp. 389\u2013401. Springer (2004)","DOI":"10.1007\/978-3-540-30551-4_35"},{"key":"720_CR24","doi-asserted-by":"crossref","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R.: Extending the tractability border for closest leaf powers. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 397\u2013408. Springer (2005)","DOI":"10.1007\/11604686_35"},{"key":"720_CR25","doi-asserted-by":"crossref","unstructured":"Ducoffe, G.: The 4-steiner root problem. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 14\u201326. Springer (2019)","DOI":"10.1007\/978-3-030-30786-8_2"},{"key":"720_CR26","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/j.dam.2018.10.028","volume":"257","author":"G Ducoffe","year":"2019","unstructured":"Ducoffe, G.: Finding cut-vertices in the square roots of a graph. Discrete Appl. Math. 257, 158\u2013174 (2019)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"720_CR27","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1007\/s00453-017-0328-y","volume":"80","author":"D Eppstein","year":"2018","unstructured":"Eppstein, D., Kindermann, P., Kobourov, S., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., Wismath, S.: On the planar split thickness of graphs. Algorithmica 80(3), 977\u2013994 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0328-y","journal-title":"Algorithmica"},{"key":"720_CR28","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: International Symposium on Algorithms and Computation, pp. 403\u2013414. Springer (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"issue":"3760","key":"720_CR29","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1126\/science.155.3760.279","volume":"155","author":"WM Fitch","year":"1967","unstructured":"Fitch, W.M., Margoliash, E.: Construction of phylogenetic trees. Science 155(3760), 279\u2013284 (1967). https:\/\/doi.org\/10.1126\/science.155.3760.279","journal-title":"Science"},{"key":"720_CR30","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Kratsch, D., Paulusma, D., Stewart, A.: Finding cactus roots in polynomial time. In: International Workshop on Combinatorial Algorithms, pp. 361\u2013372. Springer (2016)","DOI":"10.1007\/978-3-319-44543-4_28"},{"key":"720_CR31","doi-asserted-by":"publisher","unstructured":"Grohe, M.: Computing crossing numbers in quadratic time. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 231\u2013236. ACM, New York (2001). https:\/\/doi.org\/10.1145\/380752.380805","DOI":"10.1145\/380752.380805"},{"key":"720_CR32","doi-asserted-by":"crossref","unstructured":"Gurski, F., Wanke, E.: The clique-width of tree-power and leaf-power graphs. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 76\u201385. Springer (2007)","DOI":"10.1007\/978-3-540-74839-7_8"},{"issue":"1\u20132","key":"720_CR33","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/BF01917434","volume":"8","author":"R Halin","year":"1976","unstructured":"Halin, R.: S-functions for graphs. J. Geom. 8(1\u20132), 171\u2013186 (1976). https:\/\/doi.org\/10.1007\/BF01917434","journal-title":"J. Geom."},{"issue":"3","key":"720_CR34","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/j.jctb.2005.08.005","volume":"96","author":"P Hlin\u011bn\u00fd","year":"2006","unstructured":"Hlin\u011bn\u00fd, P.: Branch-width, parse trees, and monadic second-order logic for matroids. J. Combin. Theory Ser. B 96(3), 325\u2013351 (2006). https:\/\/doi.org\/10.1016\/j.jctb.2005.08.005","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"720_CR35","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1016\/j.jda.2005.06.005","volume":"4","author":"W Kennedy","year":"2006","unstructured":"Kennedy, W., Lin, G., Yan, G.: Strictly chordal graphs are leaf powers. J. Discrete Algorithms 4(4), 511\u2013525 (2006). https:\/\/doi.org\/10.1016\/j.jda.2005.06.005","journal-title":"J. Discrete Algorithms"},{"key":"720_CR36","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations, vol. 842. Springer, Berlin (1994)"},{"issue":"2","key":"720_CR37","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1145\/1150334.1150337","volume":"2","author":"LC Lau","year":"2006","unstructured":"Lau, L.C.: Bipartite roots of graphs. ACM Trans. Algorithms (TALG) 2(2), 178\u2013208 (2006)","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"720_CR38","doi-asserted-by":"publisher","first-page":"1082","DOI":"10.4153\/CJM-1970-125-1","volume":"22","author":"DR Lick","year":"1970","unstructured":"Lick, D.R., White, A.T.: k-degenerate graphs. Can. J. Math. 22, 1082\u20131096 (1970)","journal-title":"Can. J. Math."},{"issue":"3","key":"720_CR39","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983). https:\/\/doi.org\/10.1145\/2402.322385","journal-title":"J. ACM"},{"key":"720_CR40","doi-asserted-by":"crossref","unstructured":"Nguyen, N.T., et\u00a0al.: Hardness results and efficient algorithms for graph powers. In: International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 238\u2013249. Springer (2009)","DOI":"10.1007\/978-3-642-11409-0_21"},{"issue":"1","key":"720_CR41","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1195","volume":"42","author":"N Nishimura","year":"2002","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: On graph powers for leaf-labeled trees. J. Algorithms 42(1), 69\u2013108 (2002). https:\/\/doi.org\/10.1006\/jagm.2001.1195","journal-title":"J. Algorithms"},{"issue":"13","key":"720_CR42","doi-asserted-by":"publisher","first-page":"1456","DOI":"10.1016\/j.disc.2006.03.030","volume":"306","author":"D Rautenbach","year":"2006","unstructured":"Rautenbach, D.: Some remarks about leaf roots. Discrete Math. 306(13), 1456\u20131461 (2006). https:\/\/doi.org\/10.1016\/j.disc.2006.03.030","journal-title":"Discrete Math."},{"issue":"3","key":"720_CR43","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"issue":"4","key":"720_CR44","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1016\/j.disc.2009.09.004","volume":"310","author":"NN Tuy","year":"2010","unstructured":"Tuy, N.N., et al.: The square of a block graph. Discrete Math. 310(4), 734\u2013741 (2010)","journal-title":"Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00720-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00720-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00720-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,28]],"date-time":"2021-05-28T23:59:32Z","timestamp":1622246372000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00720-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,29]]},"references-count":44,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["720"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00720-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,29]]},"assertion":[{"value":"1 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}