Alphabetic Minimax Trees

DOI10.1137/0214039MaRDI QIDQ3680759zbMATH OpenOpenAlexFDO

Authors David Kirkpatrick, Maria M. Klawe

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214039

zbMATH Keywords

alphabetic treefan-out constraintsfanout reductionlinear algorithmlogical circuitsminimax valueoptimal weighted treerooted treet-ary treeupper bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15)

Recommendations

• Alphabetic minimax trees in linear time
• Alphabetic Minimax Trees of Degree at Most t
• Minimax trees in linear time with applications
• Minimax Trees in Linear Time with Applications
• scientific article; zbMATH DE number 437543

Cited in

(20)

• Optimal worst case trees
• Operations research applications of dichotomous search
• Minimax trees in linear time with applications
• Online binary minimax trees
• Optimal weight allocation in rooted trees
• scientific article; zbMATH DE number 3854454 (Why is no real title available?)
• scientific article; zbMATH DE number 4213470 (Why is no real title available?)
• The method for choosing the best r-multiple trees
• Alphabetic Minimax Trees of Degree at Most t
• The Least Weight Subsequence Problem
• Extremal properties of ?-weighted binary trees
• Ranking the Best Binary Trees
• scientific article; zbMATH DE number 1947386 (Why is no real title available?)
• scientific article; zbMATH DE number 4122014 (Why is no real title available?)
• Alphabetic minimax trees in linear time
• High Spies (or How to Win a Programming Contest)
• Tight bounds for online stable sorting
• Optimal binary search trees
• On paths in search or decision trees which require almost worst-case time
• Old and new results on alphabetic codes

This page was built for publication: Alphabetic Minimax Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3680759)