The binary identification problem for weighted trees

DOI10.1016/j.tcs.2012.06.023zbMath1250.68124OpenAlexW2004158059MaRDI QIDQ1758172

Ferdinando Cicalese, Tobias Jacobs, Caio Valentim, Eduardo Sany Laber

Publication date: 8 November 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.06.023

zbMATH Keywords

computational complexityNP-harddecision treeweighted treesbinary identification problemminimum cost strategy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Dynamic programming (90C39) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Signed and weighted graphs (05C22)

Related Items

On the tree search problem with non-uniform costs ⋮ Operations research applications of dichotomous search ⋮ Edge and pair queries-random graphs and complexity ⋮ Binary search in graphs revisited ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ On the Tree Search Problem with Non-uniform Costs ⋮ Binary Search in Graphs Revisited

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Query strategies for priced information
• On an edge ranking problem of trees and graphs
• Edge ranking and searching in partial orders
• Constructing optimal binary decision trees is NP-complete
• On the hardness of the minimum height decision tree problem
• Optimal edge ranking of trees in polynomial time
• Edge ranking of weighted trees
• Optimum binary search trees
• On Minimum Edge Ranking Spanning Trees
• On Greedy Algorithms for Decision Trees
• On the Complexity of Searching in Trees: Average-Case Minimization
• Optimal Search in Trees
• Decision Trees for Geometric Models
• Minimum average cost testing for partially ordered components
• Optimal Binary Identification Procedures