On Average Time Complexity of Decision Trees and Branching Programs

Article type: Research Article

Authors: Chikalov, Igor

Affiliations: Faculty of Calculating Mathematics and Cybernetics, Nizhni Novgorod State University, 23, Gagarina Av., Nizhni Novgorod, 603600, Russia. igor@nstl.nnov.ru

Note: [] Address for correspondence: Faculty of Calculating Mathematics and Cybernetics, Nizhni Novgorod State University, 23, Gagarina Av., Nizhni Novgorod, 603600, Russia

Abstract: This paper contains some results concerning the properties of decision trees with minimal average depth. The sufficient conditions, which allows for performing a decomposition of problem are given. The class of all information systems, which have linear upper bounds on minimal average weighted depth depending only on entropy, is described. The exponential lower bounds on the number of vertices in branching programs with minimal average weighted depth for some problems are obtained.

Keywords: decision tree, branching program, average time complexity

DOI: 10.3233/FI-1999-39401

Journal: Fundamenta Informaticae, vol. 39, no. 4, pp. 337-357, 1999