{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:54:39Z","timestamp":1787320479330,"version":"build-2736575974"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["OCENW.KLEIN.305"],"award-info":[{"award-number":["OCENW.KLEIN.305"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species (\u201ctaxa\u201d), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [ Adv. Appl. Math., 84 (2017), pp. 34\u201346] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity [Formula: see text], defined as the number of convex characters on [Formula: see text] in which each state appears on at least 2 taxa. We use this to give an algorithm with running time [Formula: see text], where [Formula: see text] is the golden ratio and [Formula: see text] is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by [Formula: see text] we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to [Formula: see text] and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees.<\/jats:p>","DOI":"10.1137\/21m1463999","type":"journal-article","created":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T04:51:59Z","timestamp":1705639919000},"page":"380-411","source":"Crossref","is-referenced-by-count":1,"title":["Convex Characters, Algorithms, and Matchings"],"prefix":"10.1137","volume":"38","author":[{"given":"Steven","family":"Kelk","sequence":"first","affiliation":[{"name":"Department of Advanced Computing Sciences (DACS), Maastricht University, 6200 MD Maastricht, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ruben","family":"Meuwese","sequence":"additional","affiliation":[{"name":"Department of Advanced Computing Sciences (DACS), Maastricht University, 6200 MD Maastricht, The Netherlands."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephan","family":"Wagner","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Uppsala Universitet, Uppsala, Sweden."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,19]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-001-8006-8"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.mcm.2010.10.003"},{"key":"ref3","series-title":"Texts Algorithmics 9","first-page":"19","volume-title":"Algorithms and Complexity in Durham 2007","author":"Bachoore E.","year":"2007"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.3390\/a12120256"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.031"},{"key":"ref6","volume-title":"Elements of Information Theory","author":"Cover T.","year":"2006","edition":"2"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"E. Deen , \nL. van Iersel , \nR. Janssen , \nM. Jones , \nY. Murakami , and \nN. Zeh  , A Near-Linear Kernel for Two-Parsimony Distance, preprint, arXiv:2211.00378, 2022.","DOI":"10.2139\/ssrn.4341383"},{"key":"ref9","volume-title":"Basic Phylogenetic Combinatorics","author":"Dress A.","year":"2012"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-015-0298-1"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.2307\/2412116"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref14","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"Fomin F.","year":"2019"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.2307\/2529676"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00062-5"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.10.003"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-017-0361-1"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"S. Kelk  and \nR. Meuwese  , Sharp Upper and Lower Bounds on a Restricted Class of Convex Characters, preprint, arXiv:2107.10871, 2021.","DOI":"10.37236\/10589"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2016.10.003"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00390"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2015.02.002"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"M. Rosenfeld  , The growth rate over trees of any family of sets defined by a monadic second order formula is semi-computable, in Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference,  \nD. Marx  , ed. SIAM, Philadelphia, 2021, pp. 776\u2013795, https:\/\/doi.org\/10.1137\/1.9781611976465.49.","DOI":"10.1137\/1.9781611976465.49"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"G. Rote  , The maximum number of minimal dominating sets in a tree, in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019,  \nT. M. Chan  , ed. SIAM, Philadelphia, 2019, pp. 1201\u20131214, https:\/\/doi.org\/10.1137\/1.9781611975482.73.","DOI":"10.1137\/1.9781611975482.73"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"C. Semple  and \nM. Steel  , Phylogenetics, Oxford University Press, Oxford, UK, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-021-04352-1"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s10440-010-9575-5"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/110845045"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1463999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T12:56:55Z","timestamp":1787317015000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1463999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,19]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/21M1463999"],"URL":"https:\/\/doi.org\/10.1137\/21m1463999","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,19]]}}}