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.68145OpenAlexW2014252825MaRDI QIDQ1575712
Michael R. Fellows, H. Todd Wareham, Tandy J. Warnow, Michael T. Hallett, Hans L. Bodlaender
Publication date: 21 August 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00342-9
Related Items (13)
Incomplete directed perfect phylogeny in linear time ⋮ Hard problems in similarity searching ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Parameterized Complexity and Approximability of the SLCS Problem ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Acyclic and star colorings of cographs ⋮ Parameterized complexity and approximability of the longest compatible sequence problem ⋮ Inferring phylogenetic trees using answer set programming ⋮ The treewidth of line graphs ⋮ Completing colored graphs to meet a target property ⋮ Unnamed Item ⋮ Tractability and hardness of flood-filling games on trees ⋮ Myhill-Nerode Methods for Hypergraphs
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
This page was built for publication: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
