Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Poset Data Structure with std::set Interface
45 views
Skip to first unread message
ssn...@gmail.com
Mar 23, 2009, 7:12:16 PM3/23/09
to
Hi All,
A recent paper (Daskalak et al, “Sorting and Selection in Posets”,
http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf )
has described a solution for the problem of sorting a
width-w poset of size n, and presents an optimal query complexity
of O(n(w + log n)) to the problem
A recent paper (Daskalak et al, “Sorting and Selection in Posets”,
http://www.siam.org/proceedings/soda/2009/SODA09_044_daskalakisc.pdf )
has described a solution for the problem of sorting a
width-w poset of size n, and presents an optimal query complexity
of O(n(w + log n)) to the problem
Does anyone knows about a data-structure which has the interface of
std::set (insert/find/erase & iterators), and is capable of
maintaining the elements of a poset with the above complexity?
Regards,
Shachar S.
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
0 new messages