Finding maximal elements of a poset's subset

Question

The problem is the following: Given a poset's subset S find the maximal elements of S.

For example consider the hass diagram of the poset in http://ndp.jct.ac.il/tutorials/Discrete/node34.html. Given a subset of it ex: {12, 2, 8} the maximal elements are 12 and 8.

I do not know if I describe precisly the problem. I think the problem might involves some sorting or computation of transitive closure but I am a little confused.

Could you give me some approach for a fast algorithm? I would like to keep it in O(n^2)

Thanks.

A little clarification. My application is using RDF graphs. Two nodes are comparable if there exists a specific edge that represent the < relation. Two nodes might be comparable if there is such an explicit relation or an implicit transitive one.

So assume that the hass diagram is exactly my RDF graph. If I start from 2 doing a depth-first search how do I know that the 8 and 12 are not comparable? They might not be explicitly but they might be implicitly.

Answer 1

You can do this in linear time if you know a minimal subset of the ordering relation: regard it as a DAG, then do a depth-first traversal to find all vertices that have no successor.