{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:37:24Z","timestamp":1742924244004,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642214578"},{"type":"electronic","value":"9783642214585"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-21458-5_13","type":"book-chapter","created":{"date-parts":[[2011,6,27]],"date-time":"2011-06-27T17:11:27Z","timestamp":1309194687000},"page":"132-146","source":"Crossref","is-referenced-by-count":2,"title":["Unique Perfect Phylogeny Is NP-Hard"],"prefix":"10.1007","author":[{"given":"Michel","family":"Habib","sequence":"first","affiliation":[]},{"given":"Juraj","family":"Stacho","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/S0097539793244587","volume":"23","author":"R. Agarwala","year":"1994","unstructured":"Agarwala, R., Fern\u00e1ndez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. SIAM Journal of Computing\u00a023, 1216\u20131224 (1994)","journal-title":"SIAM Journal of Computing"},{"key":"13_CR2","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1006\/jagm.2000.1116","volume":"37","author":"S. B\u00f6cker","year":"2000","unstructured":"B\u00f6cker, S., Bryant, D., Dress, A.W.M., Steel, M.A.: Algorithmic aspects of tree amalgamation. Journal of Algorithms\u00a037, 522\u2013537 (2000)","journal-title":"Journal of Algorithms"},{"key":"13_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.J.: Two strikes against perfect phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"13_CR4","unstructured":"Bonet, M.L., Linz, S., John, K.S.: The complexity of finding multiple solutions to betweenness and quartet compatibility. CoRR abs\/1101.2170 (2011), \n                    \n                      http:\/\/arxiv.org\/abs\/1101.2170"},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2007.10.048","volume":"393","author":"B.M. Bui-Xuan","year":"2008","unstructured":"Bui-Xuan, B.M., Habib, M., Paul, C.: Competitive graph searches. Journal Theoretical Computer Science\u00a0393, 72\u201380 (2008)","journal-title":"Journal Theoretical Computer Science"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"Buneman, P.: A characterization of rigid circuit graphs. Discrete Mathematics\u00a09, 205\u2013212 (1974)","journal-title":"Discrete Mathematics"},{"key":"13_CR7","doi-asserted-by":"publisher","first-page":"311","DOI":"10.2307\/2406441","volume":"19","author":"J. Camin","year":"1965","unstructured":"Camin, J., Sokal, R.: A method for deducing branching sequences in phylogeny. Evolution\u00a019, 311\u2013326 (1965)","journal-title":"Evolution"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0016","volume":"125","author":"N. Creignou","year":"1996","unstructured":"Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation\u00a0125, 1\u201312 (1996)","journal-title":"Information and Computation"},{"key":"13_CR9","unstructured":"Dekker, M.C.H.: Reconstruction methods for derivation trees. Master\u2019s thesis, Vrije Universiteit, Amsterdam (1986)"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1146\/annurev.es.03.110172.002235","volume":"3","author":"G.F. Estabrook","year":"1972","unstructured":"Estabrook, G.F.: Cladistic methodology: a discussion of the theoretical basis for the induction of evolutionary history. Annual Review of Ecology and Systematics\u00a03, 427\u2013456 (1972)","journal-title":"Annual Review of Ecology and Systematics"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0025-5564(75)90040-1","volume":"23","author":"G.F. Estabrook","year":"1975","unstructured":"Estabrook, G.F., Johnson Jr., C.S., McMorris, F.R.: An idealized concept of the true cladistic character. Mathematical Biosciences\u00a023, 263\u2013272 (1975)","journal-title":"Mathematical Biosciences"},{"key":"13_CR12","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(76)90141-2","volume":"16","author":"G.F. Estabrook","year":"1976","unstructured":"Estabrook, G.F., Johnson Jr., C.S., McMorris, F.R.: An algebraic analysis of cladistic characters. Discrete Mathematics\u00a016, 141\u2013147 (1976)","journal-title":"Discrete Mathematics"},{"key":"13_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0025-5564(76)90035-3","volume":"29","author":"G.F. Estabrook","year":"1976","unstructured":"Estabrook, G.F., Johnson Jr., C.S., McMorris, F.R.: A mathematical foundation for the analysis of cladistic character compatibility. Mathematical Biosciences\u00a029, 181\u2013187 (1976)","journal-title":"Mathematical Biosciences"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. North Holland (2004)","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"13_CR15","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1006\/jagm.1995.1047","volume":"19","author":"M.C. Golumbic","year":"1995","unstructured":"Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms\u00a019, 449\u2013473 (1995)","journal-title":"Journal of Algorithms"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"1108","DOI":"10.1145\/174147.169675","volume":"40","author":"M.C. Golumbic","year":"1993","unstructured":"Golumbic, M.C., Shamir, R.: Complexity and algorithms for reasoning about time: a graph-theoretic approach. Journal of the ACM\u00a040, 1108\u20131133 (1993)","journal-title":"Journal of the ACM"},{"key":"13_CR17","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/BF01894195","volume":"3","author":"A.D. Gordon","year":"1986","unstructured":"Gordon, A.D.: Consensus supertrees: The synthesis of rooted trees containing overlapping sets of labeled leaves. Journal of Classification\u00a03, 335\u2013348 (1986)","journal-title":"Journal of Classification"},{"key":"13_CR18","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"Gusfield, D.: Efficient algorithms for inferring evolutionary trees. Networks\u00a021, 19\u201328 (1991)","journal-title":"Networks"},{"key":"13_CR19","unstructured":"Habib, M., Stacho, J.: Unique perfect phylogeny is NP-hard. CoRR abs\/1011.5737 (2010), \n                    \n                      http:\/\/arxiv.org\/abs\/1011.5737"},{"key":"13_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-48321-7_27","volume-title":"Fundamentals of Computation Theory","author":"L. Juban","year":"1999","unstructured":"Juban, L.: Dichotomy theorem for the generalized unique satisfiability problem. In: Ciobanu, G., P\u0103un, G. (eds.) FCT 1999. LNCS, vol.\u00a01684, pp. 327\u2013337. Springer, Heidelberg (1999)"},{"key":"13_CR21","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1137\/0405019","volume":"5","author":"S.K. Kannan","year":"1992","unstructured":"Kannan, S.K., Warnow, T.J.: Triangulating 3-colored graphs. SIAM Journal on Discrete Mathematics\u00a05, 249\u2013258 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/978-3-642-04241-6_18","volume-title":"Algorithms in Bioinformatics","author":"F. Lam","year":"2009","unstructured":"Lam, F., Gusfield, D., Sridhar, S.: Generalizing the four gamete condition and splits equivalence theorem: Perfect phylogeny on three state characters. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 206\u2013219. Springer, Heidelberg (2009)"},{"key":"13_CR23","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2412166","volume":"21","author":"W.J. LeQuesne","year":"1972","unstructured":"LeQuesne, W.J.: Further studies on the uniquely derived character concept. Systematic Zoology\u00a021, 281\u2013288 (1972)","journal-title":"Systematic Zoology"},{"key":"13_CR24","doi-asserted-by":"publisher","first-page":"513","DOI":"10.2307\/2412469","volume":"23","author":"W.J. LeQuesne","year":"1974","unstructured":"LeQuesne, W.J.: The uniquely evolved character concept and its cladistic application. Systematic Zoology\u00a023, 513\u2013517 (1974)","journal-title":"Systematic Zoology"},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"218","DOI":"10.2307\/2412846","volume":"26","author":"W.J. LeQuesne","year":"1977","unstructured":"LeQuesne, W.J.: The uniquely evolved character concept. Systematic Zoology\u00a026, 218\u2013223 (1977)","journal-title":"Systematic Zoology"},{"key":"13_CR26","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0895480192229273","volume":"7","author":"F.R. McMorris","year":"1994","unstructured":"McMorris, F.R., Warnow, T., Wimer, T.: Triangulating vertex colored graphs. SIAM Journal on Discrete Mathematics\u00a07, 296\u2013306 (1994)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"13_CR27","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0012-365X(01)00174-1","volume":"247","author":"C. Semple","year":"2002","unstructured":"Semple, C., Steel, M.: A characterization for a set of partial partitions to define an X-tree. Discrete Mathematics\u00a0247, 169\u2013186 (2002)","journal-title":"Discrete Mathematics"},{"key":"13_CR28","volume-title":"Phylogenetics. Oxford lecture series in mathematics and its applications","author":"C. Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford lecture series in mathematics and its applications. Oxford University Press, Oxford (2003)"},{"key":"13_CR29","unstructured":"Steel, M.: Personal webpage, \n                    \n                      http:\/\/www.math.canterbury.ac.nz\/~m.steel\/"},{"key":"13_CR30","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"M. Steel","year":"1992","unstructured":"Steel, M.: The complexity of reconstructing trees from qualitative characters and subtrees. Journal of Classification\u00a09, 91\u2013116 (1992)","journal-title":"Journal of Classification"},{"key":"13_CR31","volume-title":"Introduction to Graph Theory","author":"D. West","year":"1996","unstructured":"West, D.: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs (1996)"},{"key":"13_CR32","doi-asserted-by":"publisher","first-page":"214","DOI":"10.2307\/2411550","volume":"14","author":"E.O. Wilson","year":"1965","unstructured":"Wilson, E.O.: A consistency test for phylogenies based upon contemporaneous species. Systematic Zoology\u00a014, 214\u2013220 (1965)","journal-title":"Systematic Zoology"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-21458-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T19:55:17Z","timestamp":1558295717000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-21458-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642214578","9783642214585"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-21458-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}