A cubic-vertex kernel for flip consensus tree

DOI10.1007/s00453-012-9663-1zbMath1290.68047OpenAlexW2082292526MaRDI 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/

zbMATH Keywords

NP-hard problemfixed-parameter tractabilityperfect phylogenypolynomial-time preprocessingcomputational phylogeneticsedge-modification problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A survey of parameterized algorithms and the complexity of edge modification ⋮ Faster parameterized algorithms for \textsc{Bicluster Editing} and \textsc{Flip Consensus Tree} ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration

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