On the complexity of searching in trees and partially ordered structures
DOI10.1016/J.TCS.2011.08.042zbMATH Open1228.68029OpenAlexW2007918688MaRDI QIDQ650925FDOQ650925
Marco Molinaro, Tobias Jacobs, Eduardo S. Laber, Ferdinando Cicalese
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- A threshold of ln n for approximating set cover
- On an edge ranking problem of trees and graphs
- Edge ranking and searching in partial orders
- Optimal Computer Search Trees and Variable-Length Alphabetical Codes
- On the hardness of the minimum height decision tree problem
- Optimal edge ranking of trees in polynomial time
- Edge ranking of weighted trees
- Searching ordered structures
- Optimal Search in Trees
- 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 Greedy Algorithms for Decision Trees
- 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 in Trees, Series-Parallel and Interval Orders
- Improved approximation algorithms for the average-case tree searching problem
- Minimum average cost testing for partially ordered components
- Searching in random partially ordered sets
Cited In (15)
- Binary search in graphs revisited
- Competitive Online Search Trees on Trees
- On the existence of special depth first search trees
- The query complexity of order-finding
- Searching for quicksand ideals in partially ordered sets
- Searching in Trees, Series-Parallel and Interval Orders
- Partial order multiway search
- On Dasgupta's hierarchical clustering objective and its relation to other graph parameters
- Improved approximation algorithms for the average-case tree searching problem
- Theoretical Analysis of Git Bisect
- Title not available (Why is that?)
- Partial-order analogue of the secretary problem: The binary tree case
- Title not available (Why is that?)
- Binary Search in Graphs Revisited
- Theoretical analysis of git bisect
This page was built for publication: On the complexity of searching in trees and partially ordered structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650925)
