On decision trees for (1,2)-bayesian networks

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


Bayesian Networks (BN) are convenient tool for representation of probability distribution of variables. We study time complexity of decision trees which compute values of all observable variables from BN. We consider (1,2)-BN in which each node has at most 1 entering edge, and each variable has at most 2 values. For an arbitrary (1,2)-BN we obtain lower and upper bounds on minimal depth of decision tree that differ not more than by a factor of 4, and can be computed by an algorithm which has polynomial time complexity. The number of nodes in considered decision trees can grow as exponential on number of observable variables in BN. We develop an polynomial algorithm for simulation of the work of decision trees which depth lies between the obtained bounds.
Original languageEnglish (US)
Pages (from-to)57-76
Number of pages20
JournalFundamenta Informaticae
Issue number1
StatePublished - Mar 1 2002
Externally publishedYes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2023-09-21

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Algebra and Number Theory
  • Theoretical Computer Science
  • Information Systems


Dive into the research topics of 'On decision trees for (1,2)-bayesian networks'. Together they form a unique fingerprint.

Cite this