|
|||||
 |
|
|
|
|
|
Expected
conflicts in pairs of rooted binary trees
Timothy Chu and Sean Cleary
Vol. 6 (2013), No. 3, 323–332
|
Abstract |
|
Rotation distance between rooted binary trees measures the extent of similarity of two trees with ordered leaves. There are no known polynomial-time algorithms for computing rotation distance. If there are common edges or immediately changeable edges between a pair of trees, the rotation distance problem breaks into smaller subproblems. The number of crossings or conflicts of a tree pair also gives some measure of the extent of similarity of two trees. Here we describe the distribution of common edges and immediately changeable edges between randomly selected pairs of trees via computer experiments, and examine the distribution of the amount of conflicts between such pairs. |
Keywords
random binary tree pairs
|
Mathematical Subject Classification 2010
Primary: 05C05, 68P05
|
Milestones
Received: 26 June 2012
Revised: 22 October 2012
Accepted: 23 October 2012
Published: 8 September 2013
Communicated by Robert W. Robinson
|
Authors |
| Timothy Chu | |
| Department of Computer Science The City College of New York City University of New York 160 Convent Avenue New York, NY 10031 United States |
|
| Sean Cleary | |
| Department of Mathematics The City College of New York City University of New York 160 Convent Avenue New York, NY 10031 United States |
|
| http://www.sci.ccny.cuny.edu/~cleary | |
|
