Sorting and selection in posets

DOI10.1137/070697720MaRDI QIDQ3093615zbMATH OpenOpenAlexFDO

Authors Constantinos Daskalakis, Elchanan Mossel, Samantha J. Riesenfeld, Elad Verbin, Richard Karp

Publication date 18 October 2011

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

Full work available at URL https://repository.upenn.edu/statistics_papers/410

zbMATH Keywords

chain decompositionpartially ordered setsquery complexityselectionsortingtransitive relations

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Sorting and selection in posets
• scientific article; zbMATH DE number 4041286
• Entropy and sorting.

Cited in

(24)

• On the use of binary decision diagrams for solving problems on simple games
• Scaling limits for width two partially ordered sets: the incomparability window
• Pictures from Mongolia. Extracting the top elements from a partially ordered set
• On generalized comparison-based sorting problems
• Mining posets from linear orders.
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• LRM-trees: compressed indices, adaptive sorting, and compressed permutations
• Succinct posets
• Sorting and selection in posets
• Improved approximation algorithms for the average-case tree searching problem
• Binary search in graphs revisited
• Towards optimal sorting of 16 elements
• Realization problems on reachability sequences
• A tutorial on multiobjective optimization: fundamentals and evolutionary methods
• Information lattice learning
• Many-sorted equivalence of shiny and strongly polite theories
• An efficient search strategy for hidden ideals in pointed partially ordered sets
• Algorithms for the generalized poset sorting problem
• Many-criteria dominance relations
• On instance-optimal algorithms for a generalization of nuts and bolts and generalized sorting
• An optimal algorithm for sorting in trees
• Cause I'm a genial imprecise point: outlier detection for uncertain data
• Progress in presolving for mixed integer programming
• Edge ranking and searching in partial orders

This page was built for publication: Sorting and selection in posets

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