The influence of dimensions on the complexity of computing decision trees

DOI10.1016/J.ARTINT.2025.104322MaRDI QIDQ6977005zbMATH OpenFDO

Authors Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani, Marcin Pilipczuk, Ignaz Rutter, Raimund Seidel, Manuel Sorge, Jules Wulms

Publication date 30 May 2025

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.ARTINT.2025.104322

zbMATH Keywords

decision treesmachine learningparameterized complexity

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Cites work

• Can you beat treewidth?
• Constructing optimal binary decision trees is NP-complete
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3860199 (Why is no real title available?)
• scientific article; zbMATH DE number 7625179 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• On the complexity of k-SAT
• On the parameterized complexity of multiple-interval graph problems
• Parameterized algorithms
• Parametrized complexity theory.
• Which problems have strongly exponential complexity?

This page was built for publication: The influence of dimensions on the complexity of computing decision trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6977005)