Fixed-parameter tractability for the tree assembly problem

DOI10.1016/J.TCS.2021.06.036MaRDI QIDQ2232586zbMATH OpenOpenAlexFDO

Authors Feng Shi, Jie You, Zhen Zhang, Jianxin Wang, Jing-Yi Liu

Publication date 6 October 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.06.036

zbMATH Keywords

fixed-parameter algorithmsubforest isomorphismtree editing distanceTree Assembly problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition
• Parameterized algorithms for minimum tree cut/paste distance and minimum common integer partition
• Rotation distance is fixed-parameter tractable
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• On the fixed parameter tractability of agreement-based phylogenetic distances

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• A polynomial algorithm for multiprocessor scheduling with two job lengths.
• Covering tree with stars
• Faster algorithms for the maximum common subtree isomorphism problem
• Kernelization and parameterized algorithms for covering a tree by a set of stars or paths
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• On the exact block cover problem
• Parameterized algorithms
• Parameterized algorithms for minimum tree cut/paste distance and minimum common integer partition
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• The greedy algorithm for the minimum common string partition problem
• Tractabilities for tree assembly problems

Cited in

(3)

• Parameterized algorithms for minimum tree cut/paste distance and minimum common integer partition
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees

This page was built for publication: Fixed-parameter tractability for the tree assembly problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2232586)