The randomized complexity of maintaining the minimum

DOI10.1007/3-540-61422-2_116zbMath1502.68137OpenAlexW1519872868MaRDI QIDQ5054803

Gerth Stølting Brodal, Shiva P. Chaudhuri

Publication date: 9 December 2022

Published in: Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61422-2_116

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Data structures (68P05) Randomized algorithms (68W20)

Related Items (2)

Predecessor queries in dynamic integer sets ⋮ Direct graph \(k\)-partitioning with a Kernighan-Lin like heuristic

Uses Software

• heapsort

Cites Work

• A balanced search tree O(1) worst-case update time
• An adversary-based lower bound for sorting
• Fast meldable priority queues
• Unnamed Item
• Unnamed Item

This page was built for publication: The randomized complexity of maintaining the minimum