Applied Graph Theory

Analytic complexity of cluster trees

A. I. Normov, T. M. Sadykov

Plekhanov Russian State University of Economics, Moscow, Russia

Abstract: The notion of the analytic complexity of a binary tree is introduced. This is a nonnegative integer reflecting the combinatorial structure of a tree and its most concise analytic representation. The properties of the analytic complexity of a tree are described, and how to calculate it algorithmically is explained. The developed methods are used to compare cluster trees.

Keywords: cluster analysis, binary tree, analytic complexity.

UDC: 519.172.1+517.553