On the complexity of searching in trees: average-case minimization

DOI10.1007/978-3-642-14165-2_45MaRDI QIDQ3587405zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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

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
• Approximate search strategies for weighted trees
• On the tree search problem with non-uniform costs
• Partial order multiway search
• The average complexity of depth-first search with backtracking and cutoff
• Cost-error relationships in A* tree-searching
• scientific article; zbMATH DE number 1535253 (Why is no real title available?)
• scientific article; zbMATH DE number 1400211 (Why is no real title available?)
• On paths in search or decision trees which require almost worst-case time
• 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
• The binary identification problem for weighted trees
• Average-case analysis of quicksort and binary insertion tree height using incompressibility
• 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)