On the complexity of searching in trees: average-case minimization
DOI10.1007/978-3-642-14165-2_45zbMATH Open1288.68125OpenAlexW1932722758MaRDI QIDQ3587405FDOQ3587405
Authors: Tobias Jacobs, Ferdinando Cicalese, Marco Molinaro, Eduardo S. Laber 
Publication date: 7 September 2010
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-14165-2_45
Recommendations
- Improved approximation algorithms for the average-case tree searching problem
- On the complexity of searching in trees and partially ordered structures
- Approximation strategies for generalized binary search in weighted trees
- On the tree search problem with non-uniform costs
- On the tree search problem with non-uniform costs
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (24)
- On the tree search problem with non-uniform costs
- On the Huffman and alphabetic tree problem with general cost functions
- Average time complexity of decision trees.
- Binary identification problems for weighted trees
- Approximation strategies for generalized binary search in weighted trees
- Minimizing the average searching time for an object within a graph
- An Approximation Algorithm for Binary Searching in Trees
- Average-Case Lower Bounds for Searching
- Partial order multiway search
- Approximate search strategies for weighted trees
- On the tree search problem with non-uniform costs
- The average complexity of depth-first search with backtracking and cutoff
- Cost-error relationships in A* tree-searching
- Title not available (Why is that?)
- On paths in search or decision trees which require almost worst-case time
- Title not available (Why is that?)
- Improved approximation algorithms for the average-case tree searching problem
- An approximation algorithm for binary searching in trees
- On the complexity of searching in trees and partially ordered structures
- Average-case analysis of quicksort and binary insertion tree height using incompressibility
- The binary identification problem for weighted trees
- Deterministic and probabilistic binary search in graphs
- Average-case analysis of best-first search in two representative directed acyclic graphs
- Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm
This page was built for publication: On the complexity of searching in trees: average-case minimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3587405)
