Algorithms for Decision Tree Construction

Igor Chikalov

Research output: Contribution to journalArticlepeer-review


The study of algorithms for decision tree construction was initiated in 1960s. The first algorithms are based on the separation heuristic [13, 31] that at each step tries dividing the set of objects as evenly as possible. Later Garey and Graham [28] showed that such algorithm may construct decision trees whose average depth is arbitrarily far from the minimum. Hyafil and Rivest in [35] proved NP-hardness of DT problem that is constructing a tree with the minimum average depth for a diagnostic problem over 2-valued information system and uniform probability distribution. Cox et al. in [22] showed that for a two-class problem over information system, even finding the root node attribute for an optimal tree is an NP-hard problem. © Springer-Verlag Berlin Heidelberg 2011.
Original languageEnglish (US)
Pages (from-to)61-78
Number of pages18
JournalAverage Time Complexity of Decision Trees
StatePublished - 2011

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01

ASJC Scopus subject areas

  • Library and Information Sciences
  • General Computer Science
  • Information Systems and Management


Dive into the research topics of 'Algorithms for Decision Tree Construction'. Together they form a unique fingerprint.

Cite this