Sorting and Selection in Posets
Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial pe...
Main Authors: | Daskalakis, Constantinos, Karp, Richard M, Mossel, Elchanan, Riesenfeld, Samantha J, Verbin, Elad |
---|---|
Other Authors: | Massachusetts Institute of Technology. Department of Mathematics |
Format: | Article |
Language: | English |
Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
Online Access: | https://hdl.handle.net/1721.1/134507 |
Similar Items
-
Evolutionary trees and the Ising model on the Bethe lattice: a proof of Steel’s conjecture
by: Daskalakis, Constantinos, et al.
Published: (2023) -
Connectivity and Equilibrium in Random Games
by: Daskalakis, Constantinos, et al.
Published: (2012) -
Equivalent Forms for a Poset to Be Modular Poset
by: Sundarayya P., et al.
Published: (2021-05-01) -
The topology of restricted partition posets
by: Richard Ehrenborg, et al.
Published: (2011-01-01) -
Bucshbaum simplicial posets
by: Jonathan Browder, et al.
Published: (2014-01-01)