On the complexity of searching in trees and partially ordered structures
type: Item
instance of: scholarly article
title: On the complexity of searching in trees and partially ordered structures
zbMATH Open document ID: 1228.68029
author: Ferdinando Cicalese
author: Tobias Jacobs
author: Marco Molinaro
author: Eduardo S. Laber
published in: Theoretical Computer Science
publication date: 2011-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 5987009
zbMATH Keywords: decision tree
zbMATH Keywords: search problems
zbMATH Keywords: NP-completeness
zbMATH Keywords: search in posets
zbMATH Keywords: hardness of approximability
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.08.042
OpenAlex ID: W2007918688
cites work: Code and parse trees for lossless source encoding
cites work: Lower bounds for asymmetric communication channels and distributed source coding
cites work: Approximating Optimal Binary Decision Trees
cites work: Protocols for asymmetric communication channels
cites work: Optimal Search in Trees
cites work: Searching in random partially ordered sets
cites work: Decision trees for entity identification
cites work: On Greedy Algorithms for Decision Trees
cites work: Improved approximation algorithms for the average-case tree searching problem
cites work: Q4633848
cites work: Optimal edge ranking of trees in polynomial time
cites work: Edge ranking of weighted trees
cites work: Edge ranking and searching in partial orders
cites work: Searching in Trees, Series-Parallel and Interval Orders
cites work: A threshold of ln n for approximating set cover
cites work: Q4198056
cites work: Optimal Computer Search Trees and Variable-Length Alphabetical Codes
cites work: Constructing optimal binary decision trees is NP-complete
cites work: On an edge ranking problem of trees and graphs
cites work: Q3024773
cites work: Improved bounds for asymmetric communication protocols.
cites work: An Approximation Algorithm for Binary Searching in Trees
cites work: On the hardness of the minimum height decision tree problem
cites work: Q4250211
cites work: Searching ordered structures
cites work: Minimum average cost testing for partially ordered components
cites work: Q3579429
DOI: 10.1016/J.TCS.2011.08.042
description: scientific article; zbMATH DE number 5987009