Vol. 6, No. 3, 2013

Download this article
Download this article For screen
For printing
Recent Issues

Volume 10
Issue 3, 361–539
Issue 2, 181–360
Issue 1, 1–180

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
Cover Page
Editorial Board
Editors’ Addresses
Editors’ Interests
About the Journal
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Subscriptions
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
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