Rotation distance is fixed-parameter tractable

被引：21

作者：

Cleary, Sean ^{[1
,2
]}

John, Katherine St. ^{[3
,4
]}

机构：

[1] CUNY City Coll, Dept Math, New York, NY 10031 USA

[2] CUNY, Grad Ctr, New York, NY 10031 USA

[3] CUNY Herbert H Lehman Coll, Dept Math & Comp Sci, Bronx, NY 10468 USA

[4] CUNY, Grad Ctr, Bronx, NY 10468 USA

来源：

INFORMATION PROCESSING LETTERS | 2009年 / 109卷 / 16期

基金：

美国国家科学基金会;

关键词：

Rotation distance; Analysis of algorithms; Computational complexity; Fixed parameter tractability; BINARY-TREES;

D O I：

10.1016/j.ipl.2009.04.023

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Rotation distance between trees measures the number of simple operations it takes to transform one tree into another. There are no known polynomial-time algorithms for computing rotation distance. In the case of ordered rooted trees, we show that the rotation distance between two ordered trees is fixed-parameter tractable, in the parameter, k, the rotation distance. The proof relies on the kernelization of the initial trees to trees with size bounded by 5k. (C) 2009 Published by Elsevier B.V.

引用

页码：918 / 922

页数：5

共 17 条

[1]

Allen CR, 2001, CONSERV ECOL, V5

[2] Efficient lower and upper bounds of the diagonal-flip distance between triangulations [J].

Baril, Jean-Luc ;

Pallo, Jean-Marcel .

Information Processing Letters, 2006, 100 (04) :131-136

[3] Approximating subtree distances between phylogenies [J].

Bonet, Maria Luisa ;

John, Katherine St. ;

Mahindru, Ruchi ;

Amenta, Nina .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2006, 13 (08) :1419-1434

[4]

BONET ML, 2008, IEEE ACM T IN PRESS

[5]

Bordewich M., 2005, Ann Comb, V8, P409, DOI DOI 10.1007/S00026-004-0229-Z

[6] Computing the minimum number of hybridization events for a consistent evolutionary history [J].

Bordewich, Magnus ;

Semple, Charles .

DISCRETE APPLIED MATHEMATICS, 2007, 155 (08) :914-928

[7] Bounding restricted rotation distance [J].

Cleary, S ;

Taback, J .

INFORMATION PROCESSING LETTERS, 2003, 88 (05) :251-256

[8] Restricted rotation distance between binary trees [J].

Cleary, S .

INFORMATION PROCESSING LETTERS, 2002, 84 (06) :333-338

[9] Bounding right-arm rotation distances [J].

Cleary, Sean ;

Taback, Jennifer .

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2007, 17 (02) :369-399

[10] A NOTE ON SOME TREE SIMILARITY MEASURES [J].

CULIK, K ;

WOOD, D .

INFORMATION PROCESSING LETTERS, 1982, 15 (01) :39-42

← 1 2 →