Multidimensional Divide-and-Conquer Maximin Recurrences

DOI10.1137/S0895480192232862MaRDI QIDQ4847365zbMATH OpenOpenAlexFDO

Authors L. Alonso, Edward M. Reingold, R. Schott

Publication date 20 September 1995

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmic analysisdivide-and-conquer recurrencepartition trees

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Combinatorial inequalities (05A20) Trees (05C05) Rate of growth of functions, orders of infinity, slowly varying functions (26A12) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
• A frame for general divide-and-conquer recurrences
• Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
• Solution of a Divide-and-Conquer Maximin Recurrence
• Exact balancing is not always good

Cited in

(13)

• Recurrence relations based on minimization and maximization
• An asymptotic theory for recurrence relations based on minimization and maximization.
• Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
• A typical vertex of a tree
• The optimality of a certain purely recursive dissection for a sequentially n-divisible square
• Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures
• Competitive graph searches
• Exact solution of a minimal recurrence
• Solution of a Divide-and-Conquer Maximin Recurrence
• Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
• A general framework for static cost analysis of parallel logic programs
• Multidimensional Divide-and-Conquer and Weighted Digital Sums (Extended Abstract)
• Quasiconvex analysis of backtracking algorithms

This page was built for publication: Multidimensional Divide-and-Conquer Maximin Recurrences

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