Improved approximation algorithms for the average-case tree searching problem
type: Item
instance of: scholarly article
title: Improved approximation algorithms for the average-case tree searching problem
zbMATH Open document ID: 1317.68270
author: Ferdinando Cicalese
author: Tobias Jacobs
author: Marco Molinaro
author: Eduardo S. Laber
published in: Algorithmica
publication date: 2014-12-02T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6375650
zbMATH Keywords: searching in trees
zbMATH Keywords: average case analysis
zbMATH Keywords: approximation algorithms
zbMATH Keywords: FPTAS
zbMATH Keywords: decision trees
MaRDI profile type: Publication
full work available at URL: s00453-012-9715-6
OpenAlex ID: W1985159132
cites work: Code and parse trees for lossless source encoding
cites work: Lower bounds for asymmetric communication channels and distributed source coding
cites work: Approximating Optimal Binary Decision Trees
cites work: Protocols for asymmetric communication channels
cites work: Decision Trees for Geometric Models
cites work: Optimal Search in Trees
cites work: Decision trees for entity identification
cites work: On Greedy Algorithms for Decision Trees
cites work: On the complexity of searching in trees and partially ordered structures
cites work: Sorting and Selection in Posets
cites work: Optimal edge ranking of trees in polynomial time
cites work: Edge ranking and searching in partial orders
cites work: Searching in Trees, Series-Parallel and Interval Orders
cites work: Optimal Binary Identification Procedures
cites work: A New Algorithm for Minimum Cost Binary Trees
cites work: Optimal Computer Search Trees and Variable-Length Alphabetical Codes
cites work: Constructing optimal binary decision trees is NP-complete
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: On an edge ranking problem of trees and graphs
cites work: On the Complexity of Searching in Trees: Average-Case Minimization
cites work: Analytical aspects of tie breaking
cites work: Q4057549
cites work: Q3024773
cites work: Improved bounds for asymmetric communication protocols.
cites work: An approximation algorithm for binary searching in trees
cites work: On the hardness of the minimum height decision tree problem
cites work: Q4250211
cites work: Searching ordered structures
cites work: Minimum average cost testing for partially ordered components
cites work: Q3579429
cites work: Optimal node ranking of tree in linear time
DOI: 10.1007/S00453-012-9715-6
Recommended article: On the Complexity of Searching in Trees: Average-Case Minimization
Recommended article: An Approximation Algorithm for Binary Searching in Trees
Recommended article: An approximation algorithm for binary searching in trees
Recommended article: Approximation algorithms for treewidth
Recommended article: Combinatorial Pattern Matching
Recommended article: Average-case analysis of approximate trie search
Recommended article: Improved Approximation Algorithms for Tree Alignment
Recommended article: Average-Case Lower Bounds for Searching
Recommended article: Q4515740
Recommended article: New approaches for understanding the asymptotic complexity of \(A^*\) tree searching.
description: scientific article; zbMATH DE number 6375650