I have a partially ordered set of numbers, represented as a
vector<set<int>> (e.g. if $2 \preceq 4$ in this order, then
poset contains 4). Given 2 elements $x$ and $y$, what is an efficient way to find all their minimal upper bounds (that is, those which aren't greater than any other upper bound, but there may be other upper bounds which aren't comparable to them)?
If I also maintain an inverse relation (i.e.
inverse_poset is also a
inverse_poset contains 2), I can do this:
- for each element
intersection, check if
intersectionhave a common element other than
z. If not,
zis a minimal upper bound.
Is there a better way? Especially one which doesn't need
EDIT: I didn't make it clear in the initial question, but new elements and edges can be added to the poset over time (but not removed). So any preprocessing should ideally be cheap to maintain when they are.