Optimal Randomized Algorithms for Local Sorting and Set-Maxima

DOI10.1137/0222020zbMath0770.68047OpenAlexW2030153860MaRDI QIDQ4032937

Wayne Goddard, Leonard J. Schulman, Valerie King, Claire M. 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 orderRandomized algorithmscomparison model

Mathematics Subject Classification ID

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

Related Items (6)

Counting restricted orientations of random graphs ⋮ Matching nuts and bolts faster ⋮ Acyclic orientations of random graphs ⋮ Elements of a theory of simulation. II: Sequential dynamical systems. ⋮ Monomial bases for broken circuit complexes ⋮ 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