On the complexity of searching in trees and partially ordered structures
From MaRDI portal
Publication:650925
DOI10.1016/j.tcs.2011.08.042zbMath1228.68029OpenAlexW2007918688MaRDI QIDQ650925
Marco Molinaro, Tobias Jacobs, Ferdinando Cicalese, Eduardo Sany Laber
Publication date: 7 December 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.08.042
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (7)
On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ Searching for quicksand ideals in partially ordered sets ⋮ Theoretical analysis of git bisect ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ Binary search in graphs revisited ⋮ Binary Search in Graphs Revisited ⋮ Competitive Online Search Trees on Trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved approximation algorithms for the average-case tree searching problem
- Searching in random partially ordered sets
- On an edge ranking problem of trees and graphs
- Edge ranking and searching in partial orders
- Constructing optimal binary decision trees is NP-complete
- Code and parse trees for lossless source encoding
- Protocols for asymmetric communication channels
- Improved bounds for asymmetric communication protocols.
- On the hardness of the minimum height decision tree problem
- Optimal edge ranking of trees in polynomial time
- Edge ranking of weighted trees
- On Greedy Algorithms for Decision Trees
- A threshold of ln n for approximating set cover
- Decision trees for entity identification
- An Approximation Algorithm for Binary Searching in Trees
- Approximating Optimal Binary Decision Trees
- Lower bounds for asymmetric communication channels and distributed source coding
- Searching ordered structures
- Searching in Trees, Series-Parallel and Interval Orders
- Optimal Search in Trees
- Minimum average cost testing for partially ordered components
- Optimal Computer Search Trees and Variable-Length Alphabetical Codes
This page was built for publication: On the complexity of searching in trees and partially ordered structures
