{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:39Z","timestamp":1759638639726,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030799861"},{"type":"electronic","value":"9783030799878"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-79987-8_23","type":"book-chapter","created":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:05:05Z","timestamp":1625007905000},"page":"324-339","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Complexity and Algorithms for\u00a0MUL-Tree Pruning"],"prefix":"10.1007","author":[{"given":"Mathieu","family":"Gascon","sequence":"first","affiliation":[]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[]},{"given":"Nadia","family":"El-Mabrouk","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,30]]},"reference":[{"issue":"3","key":"23_CR1","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A Aho","year":"1981","unstructured":"Aho, A., Yehoshua, S., Szymanski, T., Ullman, J.: Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10(3), 405\u2013421 (1981)","journal-title":"SIAM J. Comput."},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Bininda-Emonds, O. (ed.): Phylogenetic Supertrees Combining Information to Reveal the Tree of Life. Computational Biology, Kluwer Academic, Dordrecht (2004)","DOI":"10.1007\/978-1-4020-2330-9"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Bryant, D.: A classification of consensus methods for phylogenetics. DIMACS Ser. Discrete Math. Theor. Comput. Sci. 61, 163\u2013184 (2003)","DOI":"10.1090\/dimacs\/061\/11"},{"issue":"4","key":"23_CR4","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1016\/j.eswa.2004.12.035","volume":"28","author":"S Chou","year":"2005","unstructured":"Chou, S., Hsu, C.L.: MMDT: a multi-valued and multi-labeled decision tree classifier for data mining. Expert Syst. Appl. 28(4), 799\u2013812 (2005)","journal-title":"Expert Syst. Appl."},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/3-540-63220-4_55","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"1997","unstructured":"Crochemore, M., V\u00e9rin, R.: Direct construction of compact directed acyclic word graphs. In: Apostolico, A., Hein, J. (eds.) CPM 1997. LNCS, vol. 1264, pp. 116\u2013129. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/3-540-63220-4_55"},{"issue":"9","key":"23_CR6","doi-asserted-by":"publisher","first-page":"10731088","DOI":"10.1089\/cmb.2012.0008","volume":"19","author":"Y Cui","year":"2012","unstructured":"Cui, Y., Jansson, J., Sung, W.: Polynomial-time algorithms for building a consensus MUL-tree. J. Comput. Biol. 19(9), 10731088 (2012)","journal-title":"J. Comput. Biol."},{"key":"23_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1007\/978-3-030-00834-5_10","volume-title":"Comparative Genomics","author":"M Delabre","year":"2018","unstructured":"Delabre, M., et al.: Reconstructing the history of syntenies through super-reconciliation. In: Blanchette, M., Ouangraoua, A. (eds.) RECOMB-CG 2018. LNCS, vol. 11183, pp. 179\u2013195. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00834-5_10"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Delabre, M., et al.: Evolution through segmental duplications and losses: a super-reconciliation approach. Algorithms Mol. Biol. 499506 (2020)","DOI":"10.1186\/s13015-020-00171-4"},{"key":"23_CR10","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.jda.2013.06.001","volume":"25","author":"R Dondi","year":"2014","unstructured":"Dondi, R., El-Mabrouk, N., Swenson, K.M.: Gene tree correction for reconciliation and species tree inference: Complexity and algorithms. J. Discrete Algorithms 25, 51\u201365 (2014). https:\/\/doi.org\/10.1016\/j.jda.2013.06.001","journal-title":"J. Discrete Algorithms"},{"key":"23_CR11","series-title":"Texts in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. TCS. Springer, London (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"key":"23_CR12","series-title":"Computational Biology","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-030-10837-3_5","volume-title":"Bioinformatics and Phylogenetics","author":"N El-Mabrouk","year":"2019","unstructured":"El-Mabrouk, N., Noutahi, E.: Gene family evolution\u2014an algorithmic framework. In: Warnow, T. (ed.) Bioinformatics and Phylogenetics. CB, vol. 29, pp. 87\u2013119. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10837-3_5"},{"issue":"4","key":"23_CR13","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1109\/TCBB.2006.57","volume":"3","author":"G Ganapathy","year":"2006","unstructured":"Ganapathy, G., Goodson, B., Jansen, R., Le, H.S., Ramachandran, V., Warnow, T.: Pattern identification in biogeography. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(4), 334\u2013346 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"23_CR14","doi-asserted-by":"publisher","first-page":"132","DOI":"10.2307\/2412519","volume":"28","author":"M Goodman","year":"1979","unstructured":"Goodman, M., Czelusniak, J., Moore, G., Romero-Herrera, A., Matsuda, G.: Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst. Zool. 28, 132\u2013163 (1979)","journal-title":"Syst. Zool."},{"issue":"6","key":"23_CR15","first-page":"10071018","volume":"66","author":"W Gregg","year":"2017","unstructured":"Gregg, W., Ather, S., Hahn, M.: Gene-tree reconciliation with MUL-trees to resolve polyploidy events. Syst. Biol. 66(6), 10071018 (2017)","journal-title":"Syst. Biol."},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Huber, K., Moulton, V., Spillner, A.: Computing a consensus of multilabeled trees. In: 14th Workshop on Algorithm Engineering and Experiments (ALENEX 2012), pp. 84\u201392 (2012)","DOI":"10.1137\/1.9781611972924.9"},{"issue":"6\u20137","key":"23_CR17","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1007\/s00285-016-0993-5","volume":"73","author":"K Huber","year":"2016","unstructured":"Huber, K., Moulton, V., Steel, M., Wu, T.: Folding and unfolding phylogenetic trees and networks. J. Math. Biol. 73(6\u20137), 1761\u20131780 (2016)","journal-title":"J. Math. Biol."},{"key":"23_CR18","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Proceedings of a symposium on the Complexity of Computer Computations, held March 20\u201322, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, pp. 85\u2013103. The IBM Research Symposia Series, Plenum Press, New York (1972). https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"23_CR19","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1186\/1471-2148-9-216","volume":"9","author":"M Lott","year":"2009","unstructured":"Lott, M., Spillner, A., Huber, K.: Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evol. Biol. 9, 216 (2009)","journal-title":"BMC Evol. Biol."},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Nguyen, N., Mirarab, S., Warnow, T.: MRL and SuperFine+MRL: new supertree methods. J. Algo. for Mol. Biol. 7(3) (2012)","DOI":"10.1186\/1748-7188-7-3"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1016\/0020-7519(93)90039-2","volume":"23","author":"R Page","year":"1993","unstructured":"Page, R.: Parasites, phylogeny and cospeciation. Int. J. Parasitol. 23, 499\u2013506 (1993)","journal-title":"Int. J. Parasitol."},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0304-3975(81)90081-5","volume":"15","author":"A Paz","year":"1981","unstructured":"Paz, A., Moran, S.: Non deterministic polynomial optimization problems and their approximations. Theoret. Comput. Sci. 15, 251\u2013277 (1981). https:\/\/doi.org\/10.1016\/0304-3975(81)90081-5","journal-title":"Theoret. Comput. Sci."},{"issue":"5","key":"23_CR23","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1080\/10635150701639754","volume":"56","author":"V Ranwez","year":"2007","unstructured":"Ranwez, V., et al.: PhySIC: a veto supertree method with desirable properties. Syst. Biol. 56(5), 798\u2013817 (2007)","journal-title":"Syst. Biol."},{"key":"23_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1007\/978-3-642-00982-2_60","volume-title":"Language and Automata Theory and Applications","author":"C Scornavacca","year":"2009","unstructured":"Scornavacca, C., Berry, V., Ranwez, V.: From gene trees to species trees through a supertree approach. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 702\u2013714. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00982-2_60"},{"issue":"1","key":"23_CR25","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1016\/S0166-218X(00)00202-X","volume":"105","author":"C Semple","year":"2000","unstructured":"Semple, C., Steel, M.: A supertree method for rooted trees. Discret. Appl. Math. 105(1), 147\u2013158 (2000)","journal-title":"Discret. Appl. Math."},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1093\/bioinformatics\/17.9.821","volume":"17","author":"CM Zmasek","year":"2001","unstructured":"Zmasek, C.M., Eddy, S.R.: A simple algorithm to infer gene duplication and speciiation events on a gene tree. Bioinformatics 17, 821\u2013828 (2001)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-79987-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,29]],"date-time":"2021-06-29T23:14:04Z","timestamp":1625008444000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-79987-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030799861","9783030799878"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-79987-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"30 June 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Algorithm implementation available at .","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Availability"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ottawa, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 July 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 July 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2021.eecs.uottawa.ca\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"107","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"9.1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The workshop was held virtually.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}