Skip to main content
SpringerLink
Log in

A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

For monotonic Boolean functions, a branch-and-bound algorithm is given for constructing an optimal decision tree (sequential evaluation procedure). The tree is optimal in minimizing the average number of variables which need to be examined.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Breitbart, Y., Reiter, A.: Algorithms for fast evaluation of Boolean expressions. Acta Informatica 4, 107–116 (1975)

    Google Scholar 

  2. Reinwald, L. T., Soland, R. M.: Conversion of limited entry decision tables to optimal computer programs. I: Minimum average processing time. J. ACM 13, 339–358 (1966)

    Google Scholar 

  3. Winder, R. O.: Chow Parameters in Threshold Logic. J. ACM 18, 265–289 (1971)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Technion-Israel Institute of Technology, Technion City, Haifa, Israel

    Yu. Breitbart & A. Reiter

Authors
  1. Yu. Breitbart
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. Reiter
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Presently at Computer Science Dept. SUNY at Albany, Albany, N.Y., USA.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Breitbart, Y., Reiter, A. A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions. Acta Informatica 4, 311–319 (1975). https://doi.org/10.1007/BF00289614

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00289614

Keywords

Search

Navigation