On the computational complexity of the rooted subtree prune and regraft distance
type: Item
instance of: scholarly article
title: On the computational complexity of the rooted subtree prune and regraft distance
zbMATH Open document ID: 1059.05035
author: Magnus Bordewich
author: Charles Semple
published in: Annals of Combinatorics
publication date: 2005-02-25T00:00:00Z
full work available at URL: 613.pdf
review text: The paper proves that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard -- solving a longstanding problem. (This operation cuts off a subtree and reattaches it to another part of the tree.)
reviewed by: Péter L. Erdős
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 92D15
zbMATH DE Number: 2138552
zbMATH Keywords: rooted phylogenetic tree
zbMATH Keywords: rooted subtree prune and regraft
MaRDI profile type: Publication
OpenAlex ID: W1982901388
Wikidata QID: Q104141373
DOI: 10.1007/S00026-004-0229-Z
Recommended article: Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance
Recommended article: Distance Approximating Trees: Complexity and Algorithms
Recommended article: On the Complexity of Extracting Subtree with Keeping Distinguishability
Recommended article: Complexity and algorithms for MUL-tree pruning
Recommended article: Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract)
Recommended article: On the complexity of computing treebreadth
Recommended article: On the Complexity of Computing Treebreadth
Recommended article: Approximation and parameterized algorithms for common subtrees and edit distance between unordered trees
Recommended article: On the complexity of finding a largest common subtree of bounded degree
description: scientific article; zbMATH DE number 2138552