Data Structures' Maxima

DOI10.1137/S0097539791196603MaRDI QIDQ4376160zbMATH OpenOpenAlexFDO

Authors R. Schott, Guy Louchard, Claire Kenyon

Publication date 10 February 1998

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

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

zbMATH Keywords

Brownian bridgesdata structuresdiffusion techniquesprobabilistic analysis of algorithmsqueueing theory

Mathematics Subject Classification ID

Diffusion processes (60J60) Brownian motion (60J65) Applications of Brownian motions and diffusion theory (population genetics, absorption problems, etc.) (60J70) Queueing theory (aspects of probability theory) (60K25) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Maximum Size of Dynamic Data Structures
• The properties of random trees
• A provably fast linear-expected-time maxima-finding algorithm
• Maximum likelihood analysis of algorithms and data structures
• Data structures with dynamical random transitions

Cited in

(7)

• Distinctness of compositions of an integer: A probabilistic analysis
• An optimal dynamic interval stabbing-MAX data structure?
• scientific article; zbMATH DE number 437539 (Why is no real title available?)
• The Maximum Size of Dynamic Data Structures
• Data Structures for Traveling Salesmen
• Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence
• Random trees in queueing systems with deadlines

This page was built for publication: Data Structures' Maxima

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