An approximation algorithm for binary searching in trees

DOI10.1007/s00453-009-9325-0zbMath1211.68512OpenAlexW2089672536MaRDI QIDQ633849

Marco Molinaro, Eduardo Sany Laber

Publication date: 30 March 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9325-0

zbMATH Keywords

treespartially ordered setsapproximation algorithmsbinary search

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Approximation algorithms (68W25)

Related Items

Improved approximation algorithms for the average-case tree searching problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching in random partially ordered sets
• Linear probing and graphs
• Optimal binary search trees with costs depending on the access paths.
• Protocols for asymmetric communication channels
• Improved bounds for asymmetric communication protocols.
• A strategy for searching with different access costs.
• On the hardness of the minimum height decision tree problem
• Binary searching with nonuniform costs and its application to text retrieval
• On binary search trees
• Decision trees for entity identification
• Huffman coding with unequal letter costs
• Search in an Ordered Array Having Variable Probe Cost
• Optimal Search in Trees
• Minimum average cost testing for partially ordered components
• Near-Entropy Hotlink Assignments
• Partial alphabetic trees