{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:06Z","timestamp":1740109326172,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:00:00Z","timestamp":1644019200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T00:00:00Z","timestamp":1644019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["322869"],"award-info":[{"award-number":["322869"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"name":"University of Bergen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ($$\\texttt {cc}$$<\/jats:tex-math>cc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem$$\\texttt {cc}$$<\/jats:tex-math>cc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is at most the number of taxa, in fractional hypertreewidth$$\\texttt {cc}$$<\/jats:tex-math>cc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is at most the number of hyperedges, and in treewidth of Bayesian networks$$\\texttt {cc}$$<\/jats:tex-math>cc<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most$$2^\\texttt {cc}$$<\/jats:tex-math>2<\/mml:mn>cc<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the number of potential maximal cliques is at most$$3^\\texttt {cc}$$<\/jats:tex-math>3<\/mml:mn>cc<\/mml:mi><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and these objects can be listed in times$$O^*(2^\\texttt {cc})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>2<\/mml:mn>cc<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$O^*(3^\\texttt {cc})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>3<\/mml:mn>cc<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively, even when no edge clique cover is given as input; the$$O^*(\\cdot )$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>\u00b7<\/mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>notation omits factors polynomial in the input size. These enumeration algorithms imply$$O^*(3^\\texttt {cc})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>3<\/mml:mn>cc<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give$$O^*(4^m)$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>4<\/mml:mn>m<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time and$$O^*(3^m)$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>3<\/mml:mn>m<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithms, respectively, wherem<\/jats:italic>is the number of hyperedges. When an edge clique cover of size$$\\texttt {cc}'$$<\/jats:tex-math>cc<\/mml:mi>\u2032<\/mml:mo><\/mml:msup><\/mml:math><\/jats:alternatives><\/jats:inline-formula>is given as a part of the input we give$$O^*(2^{\\texttt {cc}'})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>2<\/mml:mn>cc<\/mml:mi>\u2032<\/mml:mo><\/mml:msup><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an$$O^*(2^n)$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>2<\/mml:mn>n<\/mml:mi><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>time algorithm for perfect phylogeny, wheren<\/jats:italic>is the number of taxa. We also give polynomial space algorithms with time complexities$$O^*(9^{\\texttt {cc}'})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>9<\/mml:mn>cc<\/mml:mi>\u2032<\/mml:mo><\/mml:msup><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>and$$O^*(9^{\\texttt {cc}+ O(\\log ^2 \\texttt {cc})})$$<\/jats:tex-math>O<\/mml:mi>\u2217<\/mml:mo><\/mml:msup>(<\/mml:mo>9<\/mml:mn>cc<\/mml:mi>+<\/mml:mo>O<\/mml:mi>(<\/mml:mo>log<\/mml:mo>2<\/mml:mn><\/mml:msup>cc<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:mrow><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for problems in this framework.<\/jats:p>","DOI":"10.1007\/s00453-022-00932-0","type":"journal-article","created":{"date-parts":[[2022,2,5]],"date-time":"2022-02-05T09:02:27Z","timestamp":1644051747000},"page":"2242-2270","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Optimal Triangulations Parameterized by Edge Clique Cover"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0861-6515","authenticated-orcid":false,"given":"Tuukka","family":"Korhonen","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,5]]},"reference":[{"issue":"3","key":"932_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1142\/S0129054100000211","volume":"11","author":"A Berry","year":"2000","unstructured":"Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci. 11(3), 397\u2013403 (2000). https:\/\/doi.org\/10.1142\/S0129054100000211","journal-title":"Int. J. Found. Comput. Sci."},{"key":"932_CR2","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets M\u00f6bius: fast subset convolution. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pp. 67\u201374. ACM (2007). https:\/\/doi.org\/10.1145\/1250790.1250801","DOI":"10.1145\/1250790.1250801"},{"key":"932_CR3","unstructured":"Bodlaender, H.L., Cai, L., Chen, J., Fellows, M.R., Telle, J.A., Marx, D.: Open problems in parameterized and exact computation\u2014IWPEC 2006. Technical Report UU-CS-2006-052, Department of Information and Computing Sciences, Utrecht University (2006). https:\/\/dspace.library.uu.nl\/handle\/1874\/22186"},{"issue":"1\u20133","key":"932_CR4","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.disc.2005.06.015","volume":"300","author":"M Bordewich","year":"2005","unstructured":"Bordewich, M., Huber, K.T., Semple, C.: Identifying phylogenetic trees. Discrete Math. 300(1\u20133), 30\u201343 (2005). https:\/\/doi.org\/10.1016\/j.disc.2005.06.015","journal-title":"Discrete Math."},{"issue":"1","key":"932_CR5","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V Bouchitt\u00e9","year":"2001","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212\u2013232 (2001). https:\/\/doi.org\/10.1137\/S0097539799359683","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"932_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","volume":"276","author":"V Bouchitt\u00e9","year":"2002","unstructured":"Bouchitt\u00e9, V., Todinca, I.: Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276(1\u20132), 17\u201332 (2002). https:\/\/doi.org\/10.1016\/S0304-3975(01)00007-X","journal-title":"Theor. Comput. Sci."},{"issue":"9","key":"932_CR7","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973)","journal-title":"Commun. ACM"},{"key":"932_CR8","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.dam.2014.12.012","volume":"216","author":"M Chapelle","year":"2017","unstructured":"Chapelle, M., Liedloff, M., Todinca, I., Villanger, Y.: Treewidth and pathwidth parameterized by the vertex cover number. Discrete Appl. Math. 216, 114\u2013129 (2017). https:\/\/doi.org\/10.1016\/j.dam.2014.12.012","journal-title":"Discrete Appl. Math."},{"key":"932_CR9","doi-asserted-by":"publisher","unstructured":"Conati, C., Gertner, A.S., VanLehn, K., Druzdzel, M.J.: On-line student modeling for coached problem solving using Bayesian networks. In: User Modeling, CISM, vol. 383, pp. 231\u2013242. Springer (1997). https:\/\/doi.org\/10.1007\/978-3-7091-2670-7_24","DOI":"10.1007\/978-3-7091-2670-7_24"},{"issue":"1","key":"932_CR10","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1137\/130947076","volume":"45","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Pilipczuk, M., Pilipczuk, M.: Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing 45(1), 67\u201383 (2016). https:\/\/doi.org\/10.1137\/130947076","journal-title":"SIAM Journal on Computing"},{"key":"932_CR11","doi-asserted-by":"publisher","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., Weller, M.: The PACE 2017 parameterized algorithms and computational experiments challenge: the second iteration. In: 12th International Symposium on Parameterized and Exact Computation, LIPIcs, vol.\u00a089, pp. 30:1\u201330:12. Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2017.30","DOI":"10.4230\/LIPIcs.IPEC.2017.30"},{"key":"932_CR12","doi-asserted-by":"publisher","unstructured":"Fischl, W., Gottlob, G., Longo, D.M., Pichler, R.: HyperBench: a benchmark and tool for hypergraphs and empirical findings. In: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 464\u2013480 (2019). https:\/\/doi.org\/10.1145\/3294052.3319683","DOI":"10.1145\/3294052.3319683"},{"key":"932_CR13","doi-asserted-by":"publisher","unstructured":"Fischl, W., Gottlob, G., Pichler, R.: General and fractional hypertree decompositions: hard and easy cases. In: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 17\u201332 (2018). https:\/\/doi.org\/10.1145\/3196959.3196962","DOI":"10.1145\/3196959.3196962"},{"key":"932_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-020-00692-9","author":"FV Fomin","year":"2020","unstructured":"Fomin, F.V., Golovach, P.A., Raymond, J.: On the tractability of optimization problems on H-graphs. Algorithmica (2020). https:\/\/doi.org\/10.1007\/s00453-020-00692-9","journal-title":"Algorithmica"},{"issue":"3","key":"932_CR15","doi-asserted-by":"publisher","first-page":"1058","DOI":"10.1137\/050643350","volume":"38","author":"FV Fomin","year":"2008","unstructured":"Fomin, F.V., Kratsch, D., Todinca, I., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38(3), 1058\u20131079 (2008). https:\/\/doi.org\/10.1137\/050643350","journal-title":"SIAM J. Comput."},{"issue":"4","key":"932_CR16","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.1007\/s00453-017-0297-1","volume":"80","author":"FV Fomin","year":"2018","unstructured":"Fomin, F.V., Liedloff, M., Montealegre, P., Todinca, I.: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques. Algorithmica 80(4), 1146\u20131169 (2018). https:\/\/doi.org\/10.1007\/s00453-017-0297-1","journal-title":"Algorithmica"},{"issue":"1","key":"932_CR17","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/140964801","volume":"44","author":"FV Fomin","year":"2015","unstructured":"Fomin, F.V., Todinca, I., Villanger, Y.: Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44(1), 54\u201387 (2015). https:\/\/doi.org\/10.1137\/140964801","journal-title":"SIAM J. Comput."},{"key":"932_CR18","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.tcs.2014.03.013","volume":"531","author":"M Furuse","year":"2014","unstructured":"Furuse, M., Yamazaki, K.: A revisit of the scheme for computing treewidth and minimum fill-in. Theor. Comput. Sci. 531, 66\u201376 (2014). https:\/\/doi.org\/10.1016\/j.tcs.2014.03.013","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"932_CR19","doi-asserted-by":"publisher","first-page":"30:1","DOI":"10.1145\/1568318.1568320","volume":"56","author":"G Gottlob","year":"2009","unstructured":"Gottlob, G., Mikl\u00f3s, Z., Schwentick, T.: Generalized hypertree decompositions: NP-hardness and tractable variants. J. ACM 56(6), 30:1-30:32 (2009). https:\/\/doi.org\/10.1145\/1568318.1568320","journal-title":"J. ACM"},{"issue":"1","key":"932_CR20","doi-asserted-by":"publisher","first-page":"4:1","DOI":"10.1145\/2636918","volume":"11","author":"M Grohe","year":"2014","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. ACM Trans. Algorithms 11(1), 4:1-4:20 (2014). https:\/\/doi.org\/10.1145\/2636918","journal-title":"ACM Trans. Algorithms"},{"key":"932_CR21","doi-asserted-by":"publisher","unstructured":"Gysel, R.: Minimal triangulation algorithms for perfect phylogeny problems. In: Language and Automata Theory and Applications\u20148th International Conference, LNCS, vol. 8370, pp. 421\u2013432. Springer (2014). https:\/\/doi.org\/10.1007\/978-3-319-04921-2_34","DOI":"10.1007\/978-3-319-04921-2_34"},{"issue":"2","key":"932_CR22","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1007\/BF02101694","volume":"22","author":"M Hasegawa","year":"1985","unstructured":"Hasegawa, M., Kishino, H., Yano, T.: Dating of the human-ape splitting by a molecular clock of mitochondrial DNA. J. Mol. Evol. 22(2), 160\u2013174 (1985)","journal-title":"J. Mol. Evol."},{"key":"932_CR23","doi-asserted-by":"publisher","unstructured":"Heggernes, P., Mancini, F., Nederlof, J., Villanger, Y.: A parameterized algorithm for chordal sandwich. In: Proceedings of 7th International Conference on Algorithms and Complexity, LNCS, vol. 6078, pp. 120\u2013130. Springer (2010). https:\/\/doi.org\/10.1007\/978-3-642-13073-1_12","DOI":"10.1007\/978-3-642-13073-1_12"},{"key":"932_CR24","unstructured":"IBM ILOG: CPLEX optimizer 12.7.1 (2017). https:\/\/www.ibm.com\/analytics\/data-science\/prescriptive-analytics\/cplex-optimizer"},{"key":"932_CR25","doi-asserted-by":"crossref","unstructured":"Jensen, F.V., Jensen, F.: Optimal junction trees. In: Proceedings of the 10th Annual Conference on Uncertainty in Artificial Intelligence, pp. 360\u2013366. Morgan Kaufmann (1994)","DOI":"10.1016\/B978-1-55860-332-5.50050-X"},{"key":"932_CR26","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-68282-2","volume-title":"Bayesian Networks and Decision Graphs","author":"FV Jensen","year":"2007","unstructured":"Jensen, F.V., Nielsen, T.D.: Bayesian Networks and Decision Graphs. Springer, Berlin (2007). https:\/\/doi.org\/10.1007\/978-0-387-68282-2"},{"issue":"6","key":"932_CR27","doi-asserted-by":"publisher","first-page":"1749","DOI":"10.1137\/S0097539794279067","volume":"26","author":"S Kannan","year":"1997","unstructured":"Kannan, S., Warnow, T.: A fast algorithm for the computation and enumeration of perfect phylogenies. SIAM J. Comput. 26(6), 1749\u20131763 (1997). https:\/\/doi.org\/10.1137\/S0097539794279067","journal-title":"SIAM J. Comput."},{"key":"932_CR28","unstructured":"Korhonen, T.: Finding optimal tree decompositions. Master\u2019s thesis, University of Helsinki (2020). http:\/\/urn.fi\/URN:NBN:fi:hulib-202006173010"},{"key":"932_CR29","doi-asserted-by":"publisher","unstructured":"Korhonen, T.: Finding optimal triangulations parameterized by edge clique cover. In: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 180, pp. 22:1\u201322:18. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2020.22","DOI":"10.4230\/LIPIcs.IPEC.2020.22"},{"key":"932_CR30","doi-asserted-by":"publisher","unstructured":"Korhonen, T., Berg, J., J\u00e4rvisalo, M.: Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitt\u00e9\u2013Todinca algorithm. ACM J. Exp. Algorithm. 24(1), 1.9:1\u20131.9:19 (2019). https:\/\/doi.org\/10.1145\/3301297","DOI":"10.1145\/3301297"},{"key":"932_CR31","doi-asserted-by":"publisher","unstructured":"Korhonen, T., J\u00e4rvisalo, M.: Finding most compatible phylogenetic trees over multi-state characters. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence, pp. 1544\u20131551. AAAI Press (2020). https:\/\/doi.org\/10.1609\/aaai.v34i02.5514","DOI":"10.1609\/aaai.v34i02.5514"},{"key":"932_CR32","doi-asserted-by":"publisher","unstructured":"Liedloff, M., Montealegre, P., Todinca, I.: Beyond classes of graphs with \u201cfew\u201d minimal separators: FPT results through potential maximal cliques. Algorithmica 81(3), 986\u20131005 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0453-2","DOI":"10.1007\/s00453-018-0453-2"},{"issue":"7","key":"932_CR33","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","volume":"158","author":"D Lokshtanov","year":"2010","unstructured":"Lokshtanov, D.: On the complexity of computing treelength. Discrete Appl. Math. 158(7), 820\u2013827 (2010). https:\/\/doi.org\/10.1016\/j.dam.2009.10.007","journal-title":"Discrete Appl. Math."},{"key":"932_CR34","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"6","key":"932_CR35","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/j.ipl.2011.12.002","volume":"112","author":"L Moll","year":"2012","unstructured":"Moll, L., Tazari, S., Thurley, M.: Computing hypergraph width measures exactly. Inf. Process. Lett. 112(6), 238\u2013242 (2012). https:\/\/doi.org\/10.1016\/j.ipl.2011.12.002","journal-title":"Inf. Process. Lett."},{"key":"932_CR36","doi-asserted-by":"publisher","unstructured":"Ravid, N., Medini, D., Kimelfeld, B.: Ranked enumeration of minimal triangulations. In: Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pp. 74\u201388. ACM (2019). https:\/\/doi.org\/10.1145\/3294052.3319678","DOI":"10.1145\/3294052.3319678"},{"issue":"1","key":"932_CR37","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1111\/1467-968X.00091","volume":"100","author":"D Ringe","year":"2002","unstructured":"Ringe, D., Warnow, T., Taylor, A.: Indo-European and computational cladistics. Trans. Philol. Soc. 100(1), 59\u2013129 (2002). https:\/\/doi.org\/10.1111\/1467-968X.00091","journal-title":"Trans. Philol. Soc."},{"issue":"3","key":"932_CR38","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v035.i03","volume":"35","author":"M Scutari","year":"2010","unstructured":"Scutari, M.: Learning Bayesian networks with the bnlearn R package. J. Stat. Softw. 35(3), 1\u201322 (2010). https:\/\/doi.org\/10.18637\/jss.v035.i03","journal-title":"J. Stat. Softw."},{"key":"932_CR39","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"issue":"15","key":"932_CR40","doi-asserted-by":"publisher","first-page":"1660","DOI":"10.1016\/j.dam.2010.05.013","volume":"158","author":"K Takata","year":"2010","unstructured":"Takata, K.: Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discrete Appl. Math. 158(15), 1660\u20131667 (2010). https:\/\/doi.org\/10.1016\/j.dam.2010.05.013","journal-title":"Discrete Appl. Math."},{"key":"932_CR41","doi-asserted-by":"publisher","unstructured":"Tamaki, H.: Computing treewidth via exact and heuristic lists of minimal separators. In: Proceedings of the Special Event on Analysis of Experimental Algorithms, LNCS, vol. 11544, pp. 219\u2013236. Springer (2019). https:\/\/doi.org\/10.1007\/978-3-030-34029-2_15","DOI":"10.1007\/978-3-030-34029-2_15"},{"issue":"4","key":"932_CR42","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","volume":"37","author":"H Tamaki","year":"2019","unstructured":"Tamaki, H.: Positive-instance driven dynamic programming for treewidth. J. Comb. Optim. 37(4), 1283\u20131311 (2019). https:\/\/doi.org\/10.1007\/s10878-018-0353-z","journal-title":"J. Comb. Optim."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00932-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00932-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00932-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T00:49:41Z","timestamp":1700182181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00932-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,5]]},"references-count":42,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["932"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00932-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,2,5]]},"assertion":[{"value":"28 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 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":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}