On the hardness of the minimum height decision tree problem
From MaRDI portal
Publication:1885823
DOI10.1016/j.dam.2004.06.002zbMath1078.68043OpenAlexW2008789644MaRDI QIDQ1885823
Loana Tito Nogueira, Eduardo Sany Laber
Publication date: 12 November 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2004.06.002
Related Items (12)
On the tree search problem with non-uniform costs ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Decision trees for function evaluation: simultaneous optimization of worst and expected cost ⋮ Theoretical analysis of git bisect ⋮ Approximating optimal binary decision trees ⋮ An approximation algorithm for binary searching in trees ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Hardness and inapproximability of minimizing adaptive distinguishing sequences ⋮ The binary identification problem for weighted trees ⋮ On Polynomial Time Constructions of Minimum Height Decision Tree ⋮ Approximating decision trees with value dependent testing costs
Cites Work
This page was built for publication: On the hardness of the minimum height decision tree problem
