Alignment of Cyclically Ordered Trees

Takuya Yoshino, Kouichi Hirata

2015

Abstract

In this paper, as unordered trees preserving the adjacency among siblings, we introduce the following three kinds of a cyclically ordered tree, that is, a biordered tree that allows both a left-to-right and a right-to-left order among siblings, a cyclic-ordered tree that allows cyclic order among siblings in a left-to-right direction and a cyclic-biordered tree that allows cyclic order among siblings in both left-to-right and right-to-left directions. Then, we design the algorithms to compute the alignment distance and the segmental alignment distance between biordered trees in O(n2D2) time and ones between cyclic-ordered trees and cyclic-biordered trees in O(n2D4) time, where n is the maximum number of nodes and D is the maximum degree in two given trees.

Paper Citation

in Harvard Style

Yoshino T. and Hirata K. (2015). Alignment of Cyclically Ordered Trees . In Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM, ISBN 978-989-758-076-5, pages 263-270. DOI: 10.5220/0005207802630270

in Bibtex Style

@conference{icpram15,
author={Takuya Yoshino and Kouichi Hirata},
title={Alignment of Cyclically Ordered Trees},
booktitle={Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,},
year={2015},
pages={263-270},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0005207802630270},
isbn={978-989-758-076-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Pattern Recognition Applications and Methods - Volume 1: ICPRAM,
TI - Alignment of Cyclically Ordered Trees
SN - 978-989-758-076-5
AU - Yoshino T.
AU - Hirata K.
PY - 2015
SP - 263
EP - 270
DO - 10.5220/0005207802630270