The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
Authors:
- Hans L. BodlaenderHBHans L. Bodlaender
- Michael R. FellowsMFMichael R. Fellows
- Michael T. HallettMHMichael T. Hallett
- H.TOdd WarehamHWH.TOdd Wareham
- Tandy J. WarnowTWTandy J. Warnow
- 1 August 2000
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 244 (1-2) , 167-188
Abstract
No abstract availableKeywords
This publication has 39 references indexed in Scilit:
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthSIAM Journal on Computing, 1996
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of GraphsJournal of Algorithms, 1996
- SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHSInternational Journal of Foundations of Computer Science, 1996
- The parameterized complexity of sequence alignment and consensusTheoretical Computer Science, 1995
- A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is FixedSIAM Journal on Computing, 1994
- Beyond NP -completeness for problems of bounded width (extended abstract): hardness for the W hierarchy1994
- The Pathwidth and Treewidth of CographsSIAM Journal on Discrete Mathematics, 1993
- Finite automata, bounded treewidth and well-quasiordering1993
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability — A surveyBIT Numerical Mathematics, 1985
- Optimization of Straight Line ProgramsSIAM Journal on Computing, 1972