Totally optimal decision trees for Boolean functions
DOI10.1016/J.DAM.2016.07.009zbMATH Open1403.94133OpenAlexW2489439241MaRDI QIDQ323025FDOQ323025
Authors: Igor Chikalov, Shahid Hussain, Mikhail Moshkov 
Publication date: 7 October 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.07.009
Recommendations
Boolean functionsspace complexitytime complexitymonotone Boolean functionstotally optimal decision trees
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Reducibility among combinatorial problems
- Title not available (Why is that?)
- Transactions on Rough Sets III
- Optimal Binary Identification Procedures
- Average time complexity of decision trees.
- Title not available (Why is that?)
- Constructing optimal binary decision trees is NP-complete
- On recognizing graph properties from adjacency matrices
- Time-space tradeoffs for branching programs
- Exact learning when irrelevant variables abound
- Complexity measures and decision tree complexity: a survey.
- Pareto-optimal patterns in logical analysis of data
- Computational complexity of Boolean functions
- Innovations in intelligent machines. 4. Recent advances in knowledge engineering
- The synthetic approach to decision table conversion
- Optimizing decision trees through heuristically guided search
- Title not available (Why is that?)
- Optimization and analysis of decision trees and rules: dynamic programming approach
- Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover
Cited In (8)
- On boolean decision trees with faulty nodes
- Time and space complexity of deterministic and nondeterministic decision trees
- Title not available (Why is that?)
- Experimental study of totally optimal decision trees
- Multi-stage optimization of decision and inhibitory trees for decision tables with many-valued decisions
- Bi-criteria optimization of decision trees with applications to data analysis
- Conversational recommendation: theoretical model and complexity analysis
- Optimal decision trees and one-time-only branching programs for symmetric Boolean functions
Uses Software
This page was built for publication: Totally optimal decision trees for Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q323025)
