The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
From MaRDI portal
Publication:1575712
DOI10.1016/S0304-3975(98)00342-9zbMath0945.68145MaRDI QIDQ1575712
Michael R. Fellows, Hans L. Bodlaender, H. Todd Wareham, Michael T. Hallett, Tandy J. Warnow
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
68R10: Graph theory (including graph drawing) in computer science
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- The complexity of reconstructing trees from qualitative characters and subtrees
- On the complexity of DNA physical mapping
- The parameterized complexity of sequence alignment and consensus
- A characterisation of rigid circuit graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
- Allocating programs containing branches and loops within a multiple processor system
- Triangulating 3-Colored Graphs
- Complete Register Allocation Problems
- Critical Load Factors in Two-Processor Distributed Systems
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Triangulating Vertex-Colored Graphs
- Inferring Evolutionary History From DNA Sequences
- A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
- Intervalizing k-colored graphs
- The Pathwidth and Treewidth of Cographs
- Triangulating Three-Colored Graphs in Linear Time and Linear Space
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
- SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- Two strikes against perfect phylogeny
- The Generation of Optimal Code for Arithmetic Expressions
- Optimization of Straight Line Programs
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Efficient algorithms for inferring evolutionary trees
