The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
type: Item
instance of: scholarly article
title: The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
zbMATH Open document ID: 0945.68145
DOI: 10.1016/S0304-3975(98)00342-9
author: Michael R. Fellows
author: Michael T. Hallett
author: H. Todd Wareham
author: Tandy J. Warnow
author: Hans L. Bodlaender
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1493482
zbMATH Keywords: fixed parameter intractability
zbMATH Keywords: triangulation of colored graphs
zbMATH Keywords: graph problems
zbMATH Keywords: complexity
MaRDI profile type: Publication
cites work: Q4273870
cites work: A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
cites work: SIMPLE ALGORITHMS FOR PERFECT PHYLOGENY AND TRIANGULATING COLORED GRAPHS
cites work: Optimization of Straight Line Programs
cites work: Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: The parameterized complexity of sequence alignment and consensus
cites work: Intervalizing k-colored graphs
cites work: Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
cites work: Two strikes against perfect phylogeny
cites work: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
cites work: The Pathwidth and Treewidth of Cographs
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: A characterisation of rigid circuit graphs
cites work: Q3139349
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q4281497
cites work: Fixed-Parameter Tractability and Completeness I: Basic Results
cites work: Fixed-parameter tractability and completeness II: On completeness for W[1]
cites work: Q4501141
cites work: Q3328583
cites work: On the complexity of DNA physical mapping
cites work: Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem
cites work: Efficient algorithms for inferring evolutionary trees
cites work: Triangulating Three-Colored Graphs in Linear Time and Linear Space
cites work: Inferring Evolutionary History From DNA Sequences
cites work: Triangulating 3-Colored Graphs
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: Triangulating Vertex-Colored Graphs
cites work: Complete Register Allocation Problems
cites work: The Generation of Optimal Code for Arithmetic Expressions
cites work: The complexity of reconstructing trees from qualitative characters and subtrees
cites work: Critical Load Factors in Two-Processor Distributed Systems
cites work: Allocating programs containing branches and loops within a multiple processor system
cites work: Q3822197
full work available at URL: s0304-3975(98)00342-9
OpenAlex ID: W2014252825
description: scientific article; zbMATH DE number 1493482