Improved approximation algorithms for the average-case tree searching problem
From MaRDI portal
Publication:476452
DOI10.1007/s00453-012-9715-6zbMath1317.68270OpenAlexW1985159132MaRDI QIDQ476452
Ferdinando Cicalese, Marco Molinaro, Tobias Jacobs, Eduardo Sany Laber
Publication date: 2 December 2014
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9715-6
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Searching and sorting (68P10) Approximation algorithms (68W25)
Related Items (3)
On Dasgupta's hierarchical clustering objective and its relation to other graph parameters ⋮ On the complexity of searching in trees and partially ordered structures ⋮ Competitive Online Search Trees on Trees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An approximation algorithm for binary searching in trees
- On the complexity of searching in trees and partially ordered structures
- 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
- Optimal node ranking of tree in linear time
- Improved bounds for asymmetric communication protocols.
- On the hardness of the minimum height decision tree problem
- Optimal edge ranking of trees in polynomial time
- Analytical aspects of tie breaking
- On Greedy Algorithms for Decision Trees
- Sorting and Selection in Posets
- Decision trees for entity identification
- Approximating Optimal Binary Decision Trees
- Lower bounds for asymmetric communication channels and distributed source coding
- On the Complexity of Searching in Trees: Average-Case Minimization
- Searching ordered structures
- Searching in Trees, Series-Parallel and Interval Orders
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- A New Algorithm for Minimum Cost Binary Trees
- Optimal Search in Trees
- Decision Trees for Geometric Models
- Minimum average cost testing for partially ordered components
- Optimal Computer Search Trees and Variable-Length Alphabetical Codes
- Optimal Binary Identification Procedures
This page was built for publication: Improved approximation algorithms for the average-case tree searching problem
