{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:25:37Z","timestamp":1774945537362,"version":"3.50.1"},"reference-count":51,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2000,8,1]],"date-time":"2000-08-01T00:00:00Z","timestamp":965088000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4733,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2000,8]]},"DOI":"10.1016\/s0304-3975(98)00342-9","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T16:02:43Z","timestamp":1027612963000},"page":"167-188","source":"Crossref","is-referenced-by-count":35,"title":["The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs"],"prefix":"10.1016","volume":"244","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael R.","family":"Fellows","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael T.","family":"Hallett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H.Todd","family":"Wareham","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tandy J.","family":"Warnow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0304-3975(98)00342-9_BIB1","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1090\/conm\/147\/01199","article-title":"Finite automata, bounded treewidth and well-quasiordering","volume":"147","author":"Abrahamson","year":"1993","journal-title":"Contemp. Math."},{"issue":"6","key":"10.1016\/S0304-3975(98)00342-9_BIB2","doi-asserted-by":"crossref","first-page":"1216","DOI":"10.1137\/S0097539793244587","article-title":"A polynomial-time algorithm for the perfect phylogeny problem when the number of character-states is fixed","volume":"23","author":"Agarwala","year":"1994","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/S0304-3975(98)00342-9_BIB3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1142\/S0129054196000038","article-title":"Fast and simple algorithms for perfect phylogeny and triangulating colored graphs","volume":"7","author":"Agarwala","year":"1996","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0201002","article-title":"Optimization of straight line programs","volume":"1","author":"Aho","year":"1972","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB5","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","article-title":"Efficient algorithms for combinatorial problems on graphs with bounded decomposability: a survey","volume":"25","author":"Arnborg","year":"1985","journal-title":"BIT"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB6","first-page":"105","article-title":"Dynamic programming algorithms on graphs with bounded tree-width","volume":"vol. 317","author":"Bodlaender","year":"1998"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB7","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB8","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(94)00251-D","article-title":"The parameterized complexity of sequence alignment and consensus","volume":"147","author":"Bodlaender","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB9","first-page":"87","article-title":"Intervalizing k-colored graphs","volume":"vol. 944","author":"Bodlaender","year":"1995"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB10","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, M.R. Fellows, M.T. Hallett, Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy, in: Proc. 26th Annu. ACM Symp. on the Theory of Computing, 1994, pp. 449\u2013458.","DOI":"10.1145\/195058.195229"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB11","first-page":"373","article-title":"Two strikes against perfect phylogeny","volume":"vol. 623","author":"Bodlaender","year":"1992"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB12","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1006\/jagm.1996.0049","article-title":"Efficient and constructive algorithms for the pathwidth and treewidth of graphs","volume":"21","author":"Bodlaender","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB13","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1137\/0406014","article-title":"The pathwidth and treewidth of cographs","volume":"6","author":"Bodlaender","year":"1993","journal-title":"SIAM J. Discrete Math."},{"issue":"6","key":"10.1016\/S0304-3975(98)00342-9_BIB14","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1109\/TSE.1981.226469","article-title":"A shortest tree algorithm for optimal assignments across space and time in distributed processor systems","volume":"SE-7","author":"Bokhari","year":"1981","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB15","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1007\/BF01758777","article-title":"Automatic generation of linear-time algorithms from predicate calculus and descriptions of problems on recursively constructed graph families","volume":"7","author":"Borie","year":"1992","journal-title":"Algorithmica"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","article-title":"A characterization of rigid circuit graphs","volume":"9","author":"Buneman","year":"1974","journal-title":"Discrete Math."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB17","unstructured":"L. Cai, J. Chen, R.G. Downey, M.R. Fellows, The parameterized complexity of short computations and factorizations, Technical report, Department of Computer Science, University of Victoria, July 1993."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB18","unstructured":"N.G. Cooper (Ed.), The human genome project, Los Alamos Sci. 20 (1992) 119."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB19","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0890-5401(90)90043-H","article-title":"The monadic second-order logic of graphs I: recognizable sets of finite graphs","volume":"85","author":"Courcelle","year":"1990","journal-title":"Inform. and Comput."},{"issue":"2","key":"10.1016\/S0304-3975(98)00342-9_BIB20","doi-asserted-by":"crossref","first-page":"224","DOI":"10.2307\/2413432","article-title":"Computational complexity of inferring phylogenies by compatibility","volume":"35","author":"Day","year":"1986","journal-title":"Systematic Zoology"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB21","doi-asserted-by":"crossref","unstructured":"R.G. Downey, P.A. Evans, M.R. Fellows, Parameterized learning complexity, in: Proc. 6th ACM Workshop on Computational Learning Theory (COLT), 1993, pp. 51\u201357.","DOI":"10.1145\/168304.168311"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB22","doi-asserted-by":"crossref","unstructured":"R.G. Downey, M.R. Fellows, Fixed-parameter intractability (extended abstract), Proc. 7th Annual Conf. on Structure in Complexity Theory (Structures\u201992), 1992, pp. 36\u201349.","DOI":"10.1109\/SCT.1992.215379"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB23","series-title":"Complexity Theory","first-page":"166","article-title":"Fixed-parameter tractability and completeness III: some structural aspects of the W-hierarchy","author":"Downey","year":"1993"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB24","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1137\/S0097539792228228","article-title":"Fixed-parameter tractability and completeness I: basic results","volume":"24","author":"Downey","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB25","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","article-title":"Fixed parameter tractability and completeness II: on completeness for W[1]","volume":"141","author":"Downey","year":"1995","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB26","first-page":"89","article-title":"The parameterized complexity of some problems in logic and linguistics","volume":"vol. 813","author":"Downey","year":"1994"},{"issue":"2","key":"10.1016\/S0304-3975(98)00342-9_BIB27","doi-asserted-by":"crossref","first-page":"146","DOI":"10.2307\/2418310","article-title":"Some concepts for the estimation of evolutionary relationships in systematic botany","volume":"3","author":"Estabrook","year":"1978","journal-title":"Systematic Botany"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB28","doi-asserted-by":"crossref","unstructured":"M.R. Fellows, M.T. Hallett, H.T. Wareham, DNA physical mapping: 3 ways difficult, in: Tom Lengauer (Ed.), Proc. 1st Annu. European Symp. on Algorithms (ESA\u201993), Lecture Notes in Computer Science, vol. 726, Springer, Berlin, pp. 157\u2013168.","DOI":"10.1007\/3-540-57273-2_52"},{"issue":"11","key":"10.1016\/S0304-3975(98)00342-9_BIB29","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1109\/32.41334","article-title":"Allocating modules to processors in a distributed system","volume":"15","author":"Fern\u00e0ndez-Baca","year":"1989","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB30","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1109\/12.277293","article-title":"Parametric module allocation on partial k-trees","volume":"42","author":"Fern\u00e0ndez-Baca","year":"1993","journal-title":"IEEE Trans. Computers"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB31","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB32","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1006\/aama.1994.1009","article-title":"On the complexity of physical mapping","volume":"15","author":"Golumbic","year":"1994","journal-title":"Adv. Appl. Math."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB33","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1016\/0196-6774(84)90006-3","article-title":"Improved dynamic programming algorithms for bandwidth minimization and the mincut linear arrangement problem","volume":"5","author":"Gurari","year":"1984","journal-title":"J. Algorithms"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB34","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary trees","volume":"21","author":"Gusfield","year":"1981","journal-title":"Networks"},{"issue":"3","key":"10.1016\/S0304-3975(98)00342-9_BIB35","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/193820.193845","article-title":"A compendium of parameterized results","volume":"25","author":"Hallett","year":"1994","journal-title":"SIGACT News"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB36","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1137\/0406023","article-title":"Triangulating three-colored graphs in linear time and linear space","volume":"2","author":"Idury","year":"1993","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB37","doi-asserted-by":"crossref","unstructured":"S. Kannan, T.J. Warnow, Inferring evolutionary history from DNA sequences, in: Proc. 31rd Annu. Symp. on Foundations of Computer Science, 1990, pp. 362\u2013371.","DOI":"10.1109\/FSCS.1990.89555"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB38","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1137\/0405019","article-title":"Triangulating 3-colored graphs","volume":"5","author":"Kannan","year":"1992","journal-title":"SIAM J. Discrete Math."},{"issue":"4","key":"10.1016\/S0304-3975(98)00342-9_BIB39","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539791222171","article-title":"Inferring evolutionary history from DNA sequences","volume":"23","author":"Kannan","year":"1994","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB40","doi-asserted-by":"crossref","first-page":"540","DOI":"10.1137\/S0097539793258143","article-title":"Pathwidth, bandwidth and completion problems to proper interval graphs with small cliques","volume":"25","author":"Kaplan","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB41","doi-asserted-by":"crossref","unstructured":"H. Kaplan, R. Shamir, R.E. Tarjan, Tractability of parameterized completion problems on chordal and interval graphs, Found Comput. Ser. (1994) 780\u2013791.","DOI":"10.1109\/SFCS.1994.365715"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB42","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1146\/annurev.es.16.110185.002243","article-title":"Compatibility methods in systematics","volume":"16","author":"Meacham","year":"1985","journal-title":"Annu. Rev. Ecol. Systematics"},{"issue":"2","key":"10.1016\/S0304-3975(98)00342-9_BIB43","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0895480192229273","article-title":"Triangulating vertex-colored graphs","volume":"7","author":"McMorris","year":"1994","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB44","unstructured":"S.-I. Nakano, T. Oguma, T. Nishizeki, A linear time algorithm for c-triangulating three-colored graphs, Trans. Inst. Electron. Inform. Commun. Eng. A 377-A (3) (1994) 543\u2013546 (in Japanese)."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB45","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","article-title":"Complete register allocation problems","volume":"4","author":"Sethi","year":"1975","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB46","doi-asserted-by":"crossref","first-page":"715","DOI":"10.1145\/321607.321620","article-title":"The generation of optimal code for arithmetic expressions","volume":"17","author":"Sethi","year":"1970","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB47","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","article-title":"The complexity of reconstructing trees from qualitative characters and subtrees","volume":"9","author":"Steel","year":"1992","journal-title":"J. Classification"},{"key":"10.1016\/S0304-3975(98)00342-9_BIB48","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1109\/TSE.1978.231502","article-title":"Critical load factors in two-processor distributed systems","volume":"SE-4","author":"Stone","year":"1978","journal-title":"IEEE Trans. Software Eng."},{"issue":"10","key":"10.1016\/S0304-3975(98)00342-9_BIB49","doi-asserted-by":"crossref","first-page":"1018","DOI":"10.1109\/TSE.1986.6313018","article-title":"Allocating programs containing branches and loops within a multiple processor system","volume":"SE-12","author":"Towsley","year":"1986","journal-title":"IEEE Trans. Software Eng."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB50","unstructured":"T. Warnow, Combinatorial algorithms for constructing phylogenetic trees, Ph.D. Thesis, University of California, Berkeley, 1991."},{"key":"10.1016\/S0304-3975(98)00342-9_BIB51","unstructured":"T.V. Wimer, Linear algorithms on k-terminal graphs, Ph.D. Thesis, Dept. Computer Science, Clemson University, 1987."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598003429?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397598003429?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T11:02:15Z","timestamp":1733310135000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397598003429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,8]]},"references-count":51,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,8]]}},"alternative-id":["S0304397598003429"],"URL":"https:\/\/doi.org\/10.1016\/s0304-3975(98)00342-9","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2000,8]]}}}