A provably fast linear-expected-time maxima-finding algorithm

DOI10.1007/BF01189991MaRDI QIDQ1329142zbMATH OpenOpenAlexFDO

Authors Mordecai J. Golin

Publication date 29 October 1995

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01189991

zbMATH Keywords

component independent distributionmove-to-front algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• LATIN 2004: Theoretical Informatics
• Fast linear expected-time algorithms for computing maxima and convex hulls
• A note on the expected time for finding maxima by list algorithms
• A Linear Time Approach to the Set Maxima Problem
• Randomized range-maxima in nearly-constant parallel time
• scientific article; zbMATH DE number 2038886
• Fast sequential and parallel algorithms for finding extremal sets
• An efficient algorithm for maxdominance, with applications
• Fast algorithms for maximizing submodular functions
• A Linear Time Algorithm for the k Maximal Sums Problem

Cites work

• scientific article; zbMATH DE number 432763 (Why is no real title available?)
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4051016 (Why is no real title available?)
• A guided tour of Chernoff bounds
• Applications of the theory of records in the study of random trees
• On Finding the Maxima of a Set of Vectors
• On the Average Number of Maxima in a Set of Vectors and Applications
• On the average number of maximal in a set of vectors

Cited in

(13)

• scientific article; zbMATH DE number 2038886 (Why is no real title available?)
• scientific article; zbMATH DE number 1444320 (Why is no real title available?)
• Maxima-finding algorithms for multidimensional samples: A two-phase approach
• A linear-time algorithm for finding an ambitus
• A volume first maxima-finding algorithm
• On constant factors in comparison-based geometric algorithms and data structures
• LATIN 2004: Theoretical Informatics
• Optimal algorithms for running max and min filters on random inputs
• Fast linear expected-time algorithms for computing maxima and convex hulls
• A Fast Algorithm for Three-Dimensional Layers of Maxima Problem
• Data Structures' Maxima
• Efficient computation for the noisy MAX
• A phase transition for the probability of being a maximum among random vectors with general iid coordinates

This page was built for publication: A provably fast linear-expected-time maxima-finding algorithm

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