Solution of a Divide-and-Conquer Maximin Recurrence

DOI10.1137/0218079zbMATH Open0692.68038OpenAlexW1986428580MaRDI QIDQ3034823FDOQ3034823

Authors: Edward M. Reingold, Zhiyuan Li 

Publication date: 1989

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

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

Recommendations

• Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence
• Multidimensional Divide-and-Conquer Maximin Recurrences
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
• Exact asymptotics of divide-and-conquer recurrences
• Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences

zbMATH Keywords

recurrence relationsdivide-and-conqueralgorithmic analysis

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99) Combinatorial inequalities (05A20) Rate of growth of functions, orders of infinity, slowly varying functions (26A12)

Cited In (16)

• On the number of hypercubic bipartitions of an integer
• Divide-and-conquer recurrences -- classification of asymptotics
• An asymptotic theory for recurrence relations based on minimization and maximization.
• Linear-time construction of treaps and Cartesian trees
• Identities and periodic oscillations of divide-and-conquer recurrences splitting at half
• Multidimensional Divide-and-Conquer Maximin Recurrences
• Exact solution of a minimal recurrence
• Solutions of two minmax recurrences in parallel processing with variable recombination overhead
• Competitive graph searches
• Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications
• A generic approach for the unranking of labeled combinatorial classes
• Title not available (Why is that?)
• The Number of 1’s in Binary Integers: Bounds and Extremal Properties
• Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
• A calculus for the random generation of labelled combinatorial structures
• Recurrence relations based on minimization and maximization

This page was built for publication: Solution of a Divide-and-Conquer Maximin Recurrence

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