A cubic-vertex kernel for flip consensus tree
From MaRDI portal
Publication:2441594
DOI10.1007/s00453-012-9663-1zbMath1290.68047MaRDI QIDQ2441594
Christian Komusiewicz, Johannes Uhlmann
Publication date: 25 March 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1760/
NP-hard problem; fixed-parameter tractability; perfect phylogeny; polynomial-time preprocessing; computational phylogenetics; edge-modification problem
68W40: Analysis of algorithms
92D15: Problems related to evolution
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A survey of parameterized algorithms and the complexity of edge modification, Refined notions of parameterized enumeration kernels with applications to matching cut enumeration, Faster parameterized algorithms for \textsc{Bicluster Editing} and \textsc{Flip Consensus Tree}
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A \(2k\) kernel for the cluster editing problem
- Graph-based data clustering with overlaps
- Polynomial kernels for 3-leaf power graph modification problems
- Graph-modeled data clustering: Exact algorithms for clique generation
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- A general method to speed up fixed-parameter-tractable algorithms
- Phylogenetic supertrees. Combining information to reveal the tree of life
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Applying modular decomposition to parameterized cluster editing problems
- Parametrized complexity theory.
- NP-completeness results for edge modification problems
- A More Relaxed Model for Graph-Based Data Clustering: s-Plex Cluster Editing
- Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
- Kernels: Annotated, Proper and Induced
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- Kernelization: New Upper and Lower Bound Techniques
- Two Edge Modification Problems without Polynomial Kernels
- Computing the Minimum Fill-In is NP-Complete
- Incomplete Directed Perfect Phylogeny
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Efficient Parameterized Preprocessing for Cluster Editing
- Efficient algorithms for inferring evolutionary trees
- Complexity classification of some edge modification problems
