Optimal Randomized Algorithms for Local Sorting and Set-Maxima

DOI10.1137/0222020MaRDI QIDQ4032937zbMATH OpenOpenAlexFDO

Authors Wayne Goddard, Valerie King, Leonard J. Schulman, Claire Kenyon

Publication date 17 May 1993

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

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

zbMATH Keywords

partial ordercomparison modelRandomized algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• On the deterministic complexity of searching local maxima
• On a randomized version of exhaustive local search
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• scientific article; zbMATH DE number 2077129
• Stochastic Algorithms: Foundations and Applications
• Randomized algorithms in combinatorial optimization: A survey
• scientific article; zbMATH DE number 780783
• Local algorithms for independent sets are half-optimal
• Randomized range-maxima in nearly-constant parallel time

Cited in

(8)

• Monomial bases for broken circuit complexes
• Acyclic orientations of random graphs
• Counting restricted orientations of random graphs
• A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset
• Elements of a theory of simulation. II: Sequential dynamical systems.
• Matching nuts and bolts faster
• Matching nuts and bolts faster
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph

This page was built for publication: Optimal Randomized Algorithms for Local Sorting and Set-Maxima

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