{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,26]],"date-time":"2026-01-26T03:58:20Z","timestamp":1769399900870,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":59,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540557197","type":"print"},{"value":"9783540472780","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55719-9_80","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:34:37Z","timestamp":1330252477000},"page":"273-283","source":"Crossref","is-referenced-by-count":98,"title":["Two strikes against perfect phylogeny"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mike R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tandy J.","family":"Warnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"22_CR1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"22_CR2","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Discr. Meth., 8:277\u2013284, 1987.","journal-title":"SIAM J. Alg. Discr. Meth."},{"key":"22_CR3","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. Technical Report 90-02, Laboratoire Bordelais de Recherche en Informatique, Bordeaux, 1990. To appear in Proceedings 4th Workshop on Graph Grammars and Their Applications to Computer Science."},{"key":"22_CR4","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs J. Algorithms, 12:308\u2013340, 1991.","journal-title":"J. Algorithms"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math., 23:11\u201324, 1989.","journal-title":"Disc. Appl. Math."},{"key":"22_CR6","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender. Dynamic programming algorithms on graphs with bounded tree-width. In Proceedings of the 15'th International Colloquium on Automata, Languages and Programming, pages 105\u2013119. Springer Verlag, Lecture Notes in Computer Science volume 317, 1988.","DOI":"10.1007\/3-540-19488-6_110"},{"key":"22_CR7","volume-title":"Technical Report RUU-CS-91-13","author":"H. L. Bodlaender","year":"1991","unstructured":"H. L. Bodlaender and T. Kloks. A simple linear time algorithm for triangulating three-colored graphs. Technical Report RUU-CS-91-13, Department of Computer Science, Utrecht University, the Netherlands, 1991. To appear in: Proceedings STACS'92."},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender and T. Kloks. Better algorithms for the pathwidth and treewidth of graphs. In Proceedings 18'th International Colloquium on Automata, Languages and Programming, pages 544\u2013555. Springer Verlag, Lecture Notes in Computer Science volume 510, 1991.","DOI":"10.1007\/3-540-54233-7_162"},{"key":"22_CR9","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender and R. H. M\u00f6hring, The pathwidth and treewidth of cographs. In Proceedings 2nd Scandinavian Workshop on Algorithm Theory, pages 301\u2013309. Springer Verlag Lecture Notes in Computer Science volume 447, 1990.","DOI":"10.1007\/3-540-52846-6_99"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"K. Booth","year":"1976","unstructured":"K. Booth and G. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comp. Syst. Sc., 13:335\u2013370, 1976.","journal-title":"J. Comp. Syst. Sc."},{"key":"22_CR11","unstructured":"R. B. Borie, R. G. Parker, and C. A. Tovey. Automatic generation of linear algorithms from predicate calculus descriptions of problems on recursive constructed graph families. Manuscript, 1988."},{"key":"22_CR12","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P. Buneman","year":"1974","unstructured":"P. Buneman. A characterization of rigid circuit graphs. Discrete Math. 9:205\u2013212, 1974.","journal-title":"Discrete Math."},{"key":"22_CR13","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1111\/j.1558-5646.1965.tb01722.x","volume":"19","author":"J. Camin","year":"1965","unstructured":"J. Camin and R. Sokal, A method for deducing branching sequences in phylogeny, Evolution 19, (1965), pp. 311\u2013326.","journal-title":"Evolution"},{"key":"22_CR14","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","volume":"85","author":"B. Courcelle","year":"1990","unstructured":"B. Courcelle. The monadic second-order logic of graphs I: Recognizable sets of finite graphs. Information and Computation, 85:12\u201375, 1990.","journal-title":"Information and Computation"},{"key":"22_CR15","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G. A. Dirac","year":"1961","unstructured":"G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. Univ. Hamburg, 25: 71\u201376, 1961.","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"22_CR16","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1146\/annurev.es.03.110172.002235","volume":"3","author":"G.F. Estabrook","year":"1972","unstructured":"G.F. Estabrook, Cladistic Methodology: a discussion of the theoretical basis for the induction of evolutionary history, Annu. Rev. Evol. Syst., 3 (1972), pp. 427\u2013456.","journal-title":"Annu. Rev. Evol. Syst."},{"key":"22_CR17","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0025-5564(75)90040-1","volume":"23","author":"G.F. Estabrook","year":"1975","unstructured":"G.F. Estabrook, C.S. Johnson, Jr. and F.R. McMorris, An idealized concept of the true cladistic character, Math. Biosci. 23, 1975, pp. 263\u2013272.","journal-title":"Math. Biosci."},{"key":"22_CR18","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0012-365X(76)90141-2","volume":"16","author":"G.F. Estabrook","year":"1976","unstructured":"G.F. Estabrook, C.S. Johnson, Jr., and F.R. McMorris, An algebraic analysis of cladistic characters, Discrete Math., 16, 1976, pp. 141\u2013147.","journal-title":"Discrete Math."},{"key":"22_CR19","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0025-5564(76)90035-3","volume":"29","author":"G.F. Estabrook","year":"1976","unstructured":"G.F. Estabrook, C.S. Johnson, Jr., and F.R. McMorris, A mathematical foundation for the analysis of cladistic character compatibility, Math. Biosci., 29, 1976, pp. 181\u2013187.","journal-title":"Math. Biosci."},{"key":"22_CR20","unstructured":"M. R. Fellows and K. Abrahamson, Cutset-Regularity Beats Well-Quasi-Ordering for Bounded Treewidth. Manuscript, Nov. 1989."},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"J. Felsenstein. Numerical methods for inferring evolutionary trees. The Quaterly Review of Biology, Vol. 57, No. 4, Dec. 1982.","DOI":"10.1086\/412935"},{"key":"22_CR22","doi-asserted-by":"crossref","unstructured":"W. M. Fitch and E. Margoliash. The construction of phylogenetic trees. Science, 155, 1967.","DOI":"10.1126\/science.155.3760.279"},{"key":"22_CR23","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"L. R. Foulds","year":"1982","unstructured":"L. R. Foulds, and R. L. Graham, The Steiner problem in phytogeny is NP-Complete. Advances in Applied Mathematics, 3:43\u201349, 1982.","journal-title":"Advances in Applied Mathematics"},{"key":"22_CR24","doi-asserted-by":"crossref","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"D. R. Fulkerson","year":"1965","unstructured":"D. R. Fulkerson and O. A. Gross. Incidence matrices and interval graphs. Pacific J. Mathematics, 15:835\u2013855, 1965.","journal-title":"Pacific J. Mathematics"},{"key":"22_CR25","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. Gavril. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Combinatorial Theory series B, 16:47\u201356, 1974.","journal-title":"J. Combinatorial Theory series B"},{"key":"22_CR26","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980."},{"key":"22_CR27","unstructured":"D. Gusfield. The Steiner tree problem in phylogeny. Technical Report 332, Department of Computer Science, Yale University, Sept. 1984."},{"key":"22_CR28","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","volume":"21","author":"D. Gusfield","year":"1991","unstructured":"D. Gusfield. Efficient algorithms for inferring evolutionary trees. Networks, 21:19\u201328, 1991.","journal-title":"Networks"},{"key":"22_CR29","unstructured":"A. Habel. Hyperedge Replacement: Grammars and Languages. PhD thesis, Univ. Bremen, 1988."},{"key":"22_CR30","unstructured":"S. Kannan and T. Warnow. Triangulating three-colored graphs. In Proceedings Second Annual ACMSIAM Symp. on Discrete Algorithms, pages 337\u2013343, San Francisco, Jan. 1991. Also to appear in SIAM J. on Discrete Mathematics."},{"key":"22_CR31","doi-asserted-by":"crossref","unstructured":"S. Kannan and T. Warnow. Inferring evolutionary history from DNA sequences. In Proceedings 31st Annual Symposium on the Foundations of Computer Science, pages 362\u2013371, St. Louis, Missouri, 1990.","DOI":"10.1109\/FSCS.1990.89555"},{"key":"22_CR32","volume-title":"PhD thesis","author":"J. Lagergren","year":"1991","unstructured":"J. Lagergren. Algorithms and Minimal Forbidden Minors for Tree-decomposable Graphs. PhD thesis, Royal Institute of Technology, Stockholm, Sweden, 1991."},{"key":"22_CR33","doi-asserted-by":"crossref","unstructured":"C. Lautemann. Efficient algorithms on context-free graph languages. In Proceedings of the 15th International Colloquium on Automata, Languages and Programming, pages 362\u2013378, 1988. Springer Verlag Lectures Notes in Computer Science volume 317.","DOI":"10.1007\/3-540-19488-6_128"},{"key":"22_CR34","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. G. Lekkerkerker","year":"1962","unstructured":"C. G. Lekkerkerker and J. Ch. Boland. Representations of a finite graph by a set of intervals on the real line, Fund. Math. 51:45\u201364, 1962.","journal-title":"Fund. Math."},{"key":"22_CR35","doi-asserted-by":"crossref","first-page":"513","DOI":"10.2307\/2412469","volume":"23","author":"W. J. LeQuesne","year":"1974","unstructured":"W. J. LeQuesne. The uniquely evolved character concept and its cladistic application, Syst. Zool., 23:513\u2013517, 1974.","journal-title":"Syst. Zool."},{"key":"22_CR36","doi-asserted-by":"crossref","first-page":"218","DOI":"10.2307\/2412846","volume":"26","author":"W. J. LeQuesne","year":"1977","unstructured":"W. J. LeQuesne. The uniquely evolved character concept. Syst. Zool., 26:218\u2013223, 1977.","journal-title":"Syst. Zool."},{"key":"22_CR37","doi-asserted-by":"crossref","first-page":"201","DOI":"10.2307\/2412604","volume":"18","author":"W.J. LeQuesne","year":"1969","unstructured":"W.J. LeQuesne, A method of selection of characters in numerical taxonomy, Syst. Zool., 18, pp. 201\u2013205, 1969.","journal-title":"Syst. Zool."},{"key":"22_CR38","doi-asserted-by":"crossref","first-page":"281","DOI":"10.2307\/2412166","volume":"21","author":"W.J. LeQuesne","year":"1972","unstructured":"W.J. LeQuesne, Further studies on the uniquely derived character concept, Syst. Zool., 21, pp. 281\u2013288, 1972.","journal-title":"Syst. Zool."},{"key":"22_CR39","doi-asserted-by":"crossref","first-page":"513","DOI":"10.2307\/2412469","volume":"23","author":"W.J. LeQuesne","year":"1974","unstructured":"W.J. LeQuesne, The uniquely evolved character concept and its cladistic application, Syst. Zool., 23, pp. 513\u2013517, 1974.","journal-title":"Syst. Zool."},{"key":"22_CR40","first-page":"416","volume-title":"Proc. Eighth International Conference on Numerical Taxonomy","author":"W.J. LeQuesne","year":"1975","unstructured":"W.J. LeQuesne, Discussion of preceeding papers, In G.F. Estabrook (ed.), Proc. Eighth International Conference on Numerical Taxonomy, pp. 416\u2013429. W.H. Freeman, San Francisco, 1975."},{"key":"22_CR41","doi-asserted-by":"crossref","first-page":"218","DOI":"10.2307\/2412846","volume":"26","author":"W.J. LeQuesne","year":"1977","unstructured":"W.J. LeQuesne, The uniquely evolved character concept, Syst. Zool., 26, pp. 218\u2013223, 1977.","journal-title":"Syst. Zool."},{"key":"22_CR42","first-page":"339","volume-title":"Proceedings 8th Internatinal Conference on Numerical Taxonomy","author":"F. R. McMorris","year":"1975","unstructured":"F. R. McMorris. Compatibility criteria for cladistic and qualitative taxonomic characters. In Proceedings 8th Internatinal Conference on Numerical Taxonomy, G.F. Estrabrook, ed., pp. 339\u2013415. W.H. Freeman, San Francisco, 1975."},{"key":"22_CR43","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/BF02462853","volume":"39","author":"F. R. McMorris","year":"1977","unstructured":"F. R. McMorris. On the compatibility of binary qualitative taxonomic characters. Bull. Math. Biol., 39:133\u2013138, 1977.","journal-title":"Bull. Math. Biol."},{"key":"22_CR44","first-page":"135","volume":"16-B","author":"F. R. McMorris","year":"1983","unstructured":"F. R. McMorris and C. A. Meacham. Partition intersection graphs. Ars Combinatorica, 16-B:135\u2013138, 1983.","journal-title":"Ars Combinatorica"},{"key":"22_CR45","unstructured":"F. R. McMorris, T. Warnow, and T. Wimer. Triangulating colored graphs. Submitted to Information Processing Letters."},{"key":"22_CR46","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1146\/annurev.es.16.110185.002243","volume":"16","author":"C. A. Meacham","year":"1985","unstructured":"C. A. Meacham and G. F. Estabrook. Compatibility methods in systematics. Annual Review of Ecology and Systematics, 16:431\u2013446, 1985.","journal-title":"Annual Review of Ecology and Systematics"},{"key":"22_CR47","doi-asserted-by":"crossref","first-page":"152","DOI":"10.7312\/dunc90660-014","volume-title":"Cladistics: Perspectives on the estimation of evolutionary history","author":"C. A. Meacham","year":"1984","unstructured":"C. A. Meacham. Evaluating characters by character compatibility analysis. In: T. Duncan and T. F. Stuessy (eds.), Cladistics: Perspectives on the estimation of evolutionary history, pp. 152\u2013165. Columbia Univ. Press: New York, 1984."},{"key":"22_CR48","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/978-3-642-69024-2_34","volume-title":"Numerical Taxonomy","author":"C. A. Meacham","year":"1983","unstructured":"C. A. Meacham. Theoretical and computational considerations of the compatibility of qualitative taxonomic characters. In: J. Felsenstein (ed.), Numerical Taxonomy, pages 304\u2013314. NATO ASI Series, volume G1. Springer-Verlag: Berlin, Heidelberg, 1983."},{"key":"22_CR49","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0012-365X(84)90164-X","volume":"49","author":"A. Proskurowski","year":"1984","unstructured":"A. Proskurowski. Separating Subgraphs in k-trees: Cables and Caterpillars. Discrete Math., 49:275\u2013285, 1984.","journal-title":"Discrete Math."},{"key":"22_CR50","doi-asserted-by":"crossref","unstructured":"B. Reed. Finding approximate separators and computing treewidth quickly. Manuscript, 1992. To appear in: Proceedings of the 24'th Annual Symposium on Theory of Computing STOC'92.","DOI":"10.1145\/129712.129734"},{"key":"22_CR51","unstructured":"N. Robertson and P. D. Seymour. Graph minors XIII: The disjoint path problem. Manuscript, September 1986."},{"key":"22_CR52","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. J. Rose","year":"1970","unstructured":"D. J. Rose. Triangulated graphs and the elimination process. J. Math. Anal. Appl., 32:597\u2013609, 1970.","journal-title":"J. Math. Anal. Appl."},{"key":"22_CR53","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0012-365X(74)90042-9","volume":"7","author":"D. J. Rose","year":"1974","unstructured":"D. J. Rose. On simple characterization of k-trees. Discrete Math., 7:317\u2013322, 1974.","journal-title":"Discrete Math."},{"key":"22_CR54","volume-title":"Report R-MATH-03\/87","author":"P. Scheffler","year":"1987","unstructured":"P. Scheffler. Linear-time algorithms for NP-complete problems restricted to partial k-trees. Report R-MATH-03\/87, Karl-Weierstrass-Institut F\u00fcr Mathematik, Berlin, GDR, 1987."},{"key":"22_CR55","volume-title":"Principles of Numerical Taxonomy","author":"R. R. Sokal","year":"1963","unstructured":"R. R. Sokal and P. H. A. Sneath. Principles of Numerical Taxonomy. W.H. Freeman, San Francisco, 1963."},{"key":"22_CR56","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, 1983."},{"key":"22_CR57","unstructured":"J. R. Walter. Representations of Rigid Circuit Graphs. Ph.D. thesis, Wayne State University."},{"key":"22_CR58","doi-asserted-by":"crossref","unstructured":"E. O. Wilson. A Consistency Test for Phylogenies Based upon Contemporaneous Species. Systematic Zoology, 14:214\u2013220.","DOI":"10.2307\/2411550"},{"key":"22_CR59","unstructured":"T. V. Wimer. Linear algorithms on k-terminal graphs. PhD thesis, Dept. of Computer Science, Clemson University, 1987."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55719-9_80.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:45Z","timestamp":1619573685000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55719-9_80"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540557197","9783540472780"],"references-count":59,"URL":"https:\/\/doi.org\/10.1007\/3-540-55719-9_80","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]}}}