{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:24:10Z","timestamp":1773275050018,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T00:00:00Z","timestamp":1683158400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,10]]},"DOI":"10.1007\/s00453-023-01131-1","type":"journal-article","created":{"date-parts":[[2023,5,4]],"date-time":"2023-05-04T18:02:27Z","timestamp":1683223347000},"page":"3003-3023","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A General Framework for Enumerating Equivalence Classes of Solutions"],"prefix":"10.1007","volume":"85","author":[{"given":"Yishu","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnaud","family":"Mary","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marie-France","family":"Sagot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9797-7592","authenticated-orcid":false,"given":"Blerina","family":"Sinaimeri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,4]]},"reference":[{"issue":"3","key":"1131_CR1","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1109\/TCBB.2008.16","volume":"5","author":"MDV Braga","year":"2008","unstructured":"Braga, M.D.V., Sagot, M., Scornavacca, C., Tannier, E.: Exploring the solution space of sorting by reversals, with experiments and an application to evolution. IEEE\/ACM Trans. Comput. Biol. Bioinf. 5(3), 348\u201356 (2008). https:\/\/doi.org\/10.1109\/TCBB.2008.16","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"issue":"2","key":"1131_CR2","doi-asserted-by":"publisher","first-page":"505","DOI":"10.7916\/D8280JSB","volume":"25","author":"SA Andersson","year":"1997","unstructured":"Andersson, S.A., Madigan, D., Perlman, M.D.: A characterization of Markov equivalence classes for acyclic digraphs. Ann. Stat. 25(2), 505\u2013541 (1997). https:\/\/doi.org\/10.7916\/D8280JSB","journal-title":"Ann. Stat."},{"issue":"3","key":"1131_CR3","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J.A., Haussler, D.H., McConnell, R.M., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987). https:\/\/doi.org\/10.1145\/28869.28873","journal-title":"J. ACM"},{"key":"1131_CR4","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s00453-016-0178-z","volume-title":"Combinatorial Pattern Matching","author":"K Narisawa","year":"2007","unstructured":"Narisawa, K., Inenaga, S., Bannai, H., Takeda, M.: Efficient computation of substring equivalence classes with suffix arrays. In: Ma, B., Zhang, K. (eds.) Combinatorial Pattern Matching, pp. 340\u2013351. Springer, Berlin (2007). https:\/\/doi.org\/10.1007\/s00453-016-0178-z"},{"issue":"10","key":"1131_CR5","doi-asserted-by":"publisher","first-page":"63","DOI":"10.4230\/DagRep.8.10.63","volume":"8","author":"H Fernau","year":"2019","unstructured":"Fernau, H., Golovach, P.A., Sagot, M.-F.: Algorithmic enumeration: output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Rep. 8(10), 63\u201386 (2019). https:\/\/doi.org\/10.4230\/DagRep.8.10.63","journal-title":"Dagstuhl Rep."},{"key":"1131_CR6","doi-asserted-by":"publisher","unstructured":"Angel, A., Koudas, N.: Efficient diversity-aware search. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. SIGMOD \u201911, pp. 781\u2013792. Association for Computing Machinery, New York, NY, USA (2011). https:\/\/doi.org\/10.1145\/1989323.1989405","DOI":"10.1145\/1989323.1989405"},{"key":"1131_CR7","doi-asserted-by":"publisher","DOI":"10.1145\/2627354","author":"C Molinaro","year":"2014","unstructured":"Molinaro, C., Sliva, A., Subrahmanian, V.S.: Super-solutions: Succinctly representing solutions in abductive annotated probabilistic temporal logic. ACM Trans. Comput. Logic (2014). https:\/\/doi.org\/10.1145\/2627354","journal-title":"ACM Trans. Comput. Logic"},{"key":"1131_CR8","doi-asserted-by":"publisher","first-page":"415","DOI":"10.3934\/amc.2015.9.415","volume":"9","author":"K Morrison","year":"2015","unstructured":"Morrison, K.: An enumeration of the equivalence classes of self-dual matrix codes. Adv. Math. Commun. 9, 415 (2015). https:\/\/doi.org\/10.3934\/amc.2015.9.415","journal-title":"Adv. Math. Commun."},{"issue":"12","key":"1131_CR9","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1145\/359657.359664","volume":"21","author":"A Martelli","year":"1978","unstructured":"Martelli, A., Montanari, U.: Optimizing decision trees through heuristically guided search. Commun. ACM 21(12), 1025\u20131039 (1978). https:\/\/doi.org\/10.1145\/359657.359664","journal-title":"Commun. ACM"},{"key":"1131_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09438-9","volume-title":"Principles of Artificial Intelligence","author":"NJ Nilsson","year":"1982","unstructured":"Nilsson, N.J.: Principles of Artificial Intelligence. Springer, Palo Alto (1982)"},{"issue":"2","key":"1131_CR11","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.artint.2006.11.003","volume":"171","author":"R Dechter","year":"2007","unstructured":"Dechter, R., Mateescu, R.: And\/or search spaces for graphical models. Artif. Intell. 171(2), 73\u2013106 (2007). https:\/\/doi.org\/10.1016\/j.artint.2006.11.003","journal-title":"Artif. Intell."},{"issue":"4","key":"1131_CR12","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1145\/322276.322285","volume":"28","author":"S Gnesi","year":"1981","unstructured":"Gnesi, S., Montanari, U., Martelli, A.: Dynamic programming as graph searching: an algebraic approach. J. ACM 28(4), 737\u2013751 (1981). https:\/\/doi.org\/10.1145\/322276.322285","journal-title":"J. ACM"},{"issue":"3","key":"1131_CR13","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1137\/0115060","volume":"15","author":"RM Karp","year":"1967","unstructured":"Karp, R.M., Held, M.: Finite-state processes and dynamic programming. SIAM J. Appl. Math. 15(3), 693\u2013718 (1967). https:\/\/doi.org\/10.1137\/0115060","journal-title":"SIAM J. Appl. Math."},{"key":"1131_CR14","volume-title":"Dynamic Programming. Dover Books on Computer Science","author":"R Bellman","year":"2013","unstructured":"Bellman, R.: Dynamic Programming. Dover Books on Computer Science. Dover Publications, Mineola (2013)"},{"key":"1131_CR15","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1145\/321607.321616","volume":"17","author":"PE Bonzon","year":"1970","unstructured":"Bonzon, P.E.: Necessary and sufficient conditions for dynamic programming of combinatorial type. J. ACM 17, 675\u2013682 (1970). https:\/\/doi.org\/10.1145\/321607.321616","journal-title":"J. ACM"},{"key":"1131_CR16","doi-asserted-by":"publisher","first-page":"938","DOI":"10.1007\/s00453-009-9385-1","volume":"60","author":"J Buresh-Oppenheim","year":"2011","unstructured":"Buresh-Oppenheim, J., Davis, S., Impagliazzo, R.: A stronger model of dynamic programming algorithms. Algorithmica 60, 938\u2013968 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9385-1","journal-title":"Algorithmica"},{"issue":"1","key":"1131_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1145\/58562.59304","volume":"36","author":"P Helman","year":"1989","unstructured":"Helman, P.: A common schema for dynamic programming and branch and bound algorithms. J. ACM 36(1), 97\u2013128 (1989). https:\/\/doi.org\/10.1145\/58562.59304","journal-title":"J. ACM"},{"key":"1131_CR18","volume-title":"Nonserial Dynamic Programming","author":"U Bertele","year":"1972","unstructured":"Bertele, U., Brioschi, F.: Nonserial Dynamic Programming. Academic Press Inc, USA (1972)"},{"issue":"1","key":"1131_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1145\/321105.321111","volume":"9","author":"R Bellman","year":"1962","unstructured":"Bellman, R.: Dynamic programming treatment of the travelling salesman problem. J. ACM 9(1), 61\u201363 (1962). https:\/\/doi.org\/10.1145\/321105.321111","journal-title":"J. ACM"},{"issue":"1","key":"1131_CR20","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1137\/0110015","volume":"10","author":"M Held","year":"1962","unstructured":"Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. Soc. Ind. Appl. Math. 10(1), 196\u2013210 (1962). https:\/\/doi.org\/10.1137\/0110015","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"1131_CR21","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-540-24777-7_2","volume-title":"Basic Algorithmic Concepts","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Basic Algorithmic Concepts, pp. 15\u201342. Springer, Berlin (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7_2"},{"issue":"1","key":"1131_CR22","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. J. ACM 21(1), 168\u2013173 (1974). https:\/\/doi.org\/10.1145\/321796.321811","journal-title":"J. ACM"},{"issue":"1","key":"1131_CR23","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/S0022-0000(74)80024-3","volume":"8","author":"T Ibaraki","year":"1974","unstructured":"Ibaraki, T.: Classes of discrete optimization problems and their decision problems. J. Comput. Syst. Sci. 8(1), 84\u2013116 (1974). https:\/\/doi.org\/10.1016\/S0022-0000(74)80024-3","journal-title":"J. Comput. Syst. Sci."},{"key":"1131_CR24","doi-asserted-by":"publisher","DOI":"10.1142\/9097","volume-title":"Data Mining with Decision Trees: Theory and Applications. Series in Machine Perception and Artificial Intelligence","author":"L Rokach","year":"2008","unstructured":"Rokach, L., Maimon, O.Z.: Data Mining with Decision Trees: Theory and Applications. Series in Machine Perception and Artificial Intelligence. World Scientific, Singapore (2008). https:\/\/doi.org\/10.1142\/9097"},{"issue":"1","key":"1131_CR25","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1023\/B:VISI.0000042934.15159.49","volume":"61","author":"PF Felzenszwalb","year":"2005","unstructured":"Felzenszwalb, P.F., Huttenlocher, D.P.: Pictorial structures for object recognition. Int. J. Comput. Vis. 61(1), 55\u201379 (2005). https:\/\/doi.org\/10.1023\/B:VISI.0000042934.15159.49","journal-title":"Int. J. Comput. Vis."},{"key":"1131_CR26","doi-asserted-by":"publisher","unstructured":"Veksler, O.: Stereo correspondence by dynamic programming on a tree. In: 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR\u201905), vol. 2, pp. 384\u2013390 (2005). https:\/\/doi.org\/10.1109\/CVPR.2005.334","DOI":"10.1109\/CVPR.2005.334"},{"issue":"12","key":"1131_CR27","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1093\/bioinformatics\/bts225","volume":"28","author":"MS Bansal","year":"2012","unstructured":"Bansal, M.S., Alm, E.J., Kellis, M.: Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics 28(12), 283\u2013291 (2012). https:\/\/doi.org\/10.1093\/bioinformatics\/bts225","journal-title":"Bioinformatics"},{"issue":"1","key":"1131_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1186\/s13015-014-0031-3","volume":"10","author":"B Donati","year":"2015","unstructured":"Donati, B., Baudet, C., Sinaimeri, B., Crescenzi, P., Sagot, M.: Eucalypt: efficient tree reconciliation enumerator. Algorithms Mol. Biol. 10(1), 3 (2015). https:\/\/doi.org\/10.1186\/s13015-014-0031-3","journal-title":"Algorithms Mol. Biol."},{"issue":"1","key":"1131_CR29","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D Sankoff","year":"1975","unstructured":"Sankoff, D.: Minimal mutation trees of sequences. SIAM J. Appl. Math. 28(1), 35\u201342 (1975). https:\/\/doi.org\/10.1137\/0128004","journal-title":"SIAM J. Appl. Math."},{"issue":"12","key":"1131_CR30","doi-asserted-by":"publisher","first-page":"1497","DOI":"10.1109\/PROC.1980.11899","volume":"68","author":"WK Hale","year":"1980","unstructured":"Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497\u20131514 (1980). https:\/\/doi.org\/10.1109\/PROC.1980.11899","journal-title":"Proc. IEEE"},{"issue":"2","key":"1131_CR31","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0012-365X(91)90258-4","volume":"93","author":"FS Roberts","year":"1991","unstructured":"Roberts, F.S.: T-colorings of graphs: recent results and open problems. Discret. Math. 93(2), 229\u2013245 (1991). https:\/\/doi.org\/10.1016\/0012-365X(91)90258-4","journal-title":"Discret. Math."},{"issue":"3","key":"1131_CR32","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0166-218X(93)90015-G","volume":"45","author":"BA Tesman","year":"1993","unstructured":"Tesman, B.A.: List t-colorings of graphs. Discret. Appl. Math. 45(3), 277\u2013289 (1993). https:\/\/doi.org\/10.1016\/0166-218X(93)90015-G","journal-title":"Discret. Appl. Math."},{"key":"1131_CR33","first-page":"350","volume-title":"Tangled Trees: Phylogeny, Cospeciation, and Coevolution","author":"RDM Page","year":"2003","unstructured":"Page, R.D.M.: Tangled Trees: Phylogeny, Cospeciation, and Coevolution, p. 350. The University of Chicago Press, Chicago (2003)"},{"issue":"14","key":"1131_CR34","doi-asserted-by":"publisher","first-page":"4197","DOI":"10.1093\/bioinformatics\/btaa498","volume":"36","author":"Y Wang","year":"2020","unstructured":"Wang, Y., Mary, A., Sagot, M., Sinaimeri, B.: Capybara: equivalence class enumeration of cophylogeny event-based reconciliations. Bioinformatics 36(14), 4197\u20134199 (2020). https:\/\/doi.org\/10.1093\/bioinformatics\/btaa498","journal-title":"Bioinformatics"},{"key":"1131_CR35","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Automata, Languages and Programming","author":"HL Bodlaender","year":"1988","unstructured":"Bodlaender, H.L.: Dynamic programming on graphs with bounded treewidth. In: Lepist\u00f6, T., Salomaa, A. (eds.) Automata, Languages and Programming, pp. 105\u2013118. Springer, Berlin (1988). https:\/\/doi.org\/10.1007\/3-540-19488-6_110"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01131-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01131-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01131-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T14:07:27Z","timestamp":1695737247000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01131-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,4]]},"references-count":35,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["1131"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01131-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,4]]},"assertion":[{"value":"14 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2023","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 interests"}}]}}