May 22, Spring Quarter 2009: Thoery Seminar
1:00pm in 253 ICS
Sorting and Selection in Posets
By Constantinos Daskalakis, Richard M. Karp , Elchanan Mossel, Samantha Riesenfeld, Elad Verbin
Presented by Lowell Trott, UCI
The authors have presented several results in sorting and selection in
partially ordered sets. This includes an algorithm that sorts a
width- w poset of size n with optimal query complexity O(n(w + logn)).