Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition

DOI10.1016/j.tcs.2019.04.003zbMath1436.68149OpenAlexW2944385240WikidataQ127900434 ScholiaQ127900434MaRDI QIDQ2285134

Qilong Feng, Feng Shi, Jie You, Jianxin Wang

Publication date: 16 January 2020

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

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

zbMATH Keywords

fixed-parameter tractabilityminimum common string partitionminimum common integer partition

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Combinatorial aspects of partitions of integers (05A17) Computational methods for problems pertaining to biology (92-08) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

An improved approximation algorithm for the minimum common integer partition problem

Uses Software

• MSOAR

Cites Work

• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Minimum common string partition revisited
• Approximating maximum agreement forest on multiple binary trees
• A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
• An improved linear kernel for complementary maximal strip recovery: simpler and smaller
• An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem
• Better Approximations for the Minimum Common Integer Partition Problem
• The Tree-to-Tree Correction Problem
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• On the minimum common integer partition problem
• Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable

This page was built for publication: Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition