Please help me in improving the time complexity of the following algorithm.
Hasse Diagram(Skip this section if you already know what is Hasse Diagram, Please directly go to next section):
Consider a partially ordered set (poset, for short) (A,⊆), where A is a set and ⊆ a partial order. Each node of the diagram is an element of the poset, and if two elements x and y are connected by a line then x ⊆ y or y ⊆ x . The position of the elements and the connections are drawn respecting the following rules:
If x ⊆ y in the poset, then the point corresponding to x appears below the point corresponding to y.
The transitivity of the poset is graphically omitted, that is, if x ⊆ y and y ⊆ z, then, by transitivity of the partial order ⊆, x ⊆ z. In this case the connection x-z is omitted.
Similarly reflexivity is graphically omitted.
Hasse Diagram representation of the Poset(S={{1,2,3,5}, {2,3}, {5}, {3}, {1,3}, {1,5}}, ⊆) is as follows(only the edges are reported)
{1,2,3,5}->{2,3}
{1,2,3,5}->{1,3}
{1,2,3,5}->{1,5}
{2,3}->{3}
{1,3}->{3}
{1,5}->{5}
My initial thought
The only algorithm i could think of is O(N^2) as follows:
Read the first element is S and insert it as a first element in Hasse Diagram. As we read the next elements insert them in the already constructed diagram either in the right position (Suppose the diagram constructed till now has K elements, then it takes O(K) time to insert a new element in the right place). This way O(N ^ 2) is evident.
But i'm thinking whether sorting the elements of poset S could help but sorted order for complete elements in S cannot be built as ⊆ may not hold for all the pair of elements(Example, consider {2,3} & {1,3}).
Any ideas for improving the worst case complexity is welcomed!!
Thanks.
P.S: This is not a homework problem!!
if the set is {1,2,3,5}, the subset will be ({Æ},{1},{2},{3},{5},{1,2},{1,3],{1,5},{2,3}{2,5},{3,5},{1,2,3}{1,3,5},{1,2,5},{2,3,5},{1,2,3,5}). after taking off transitive relations we will have ({{Æ}},{1},{2},[3},{4},{5},{1,2},{2,3}{1,5},{2,5},{3,5},{1,2,3},{1,3,5},{1,2,5},{1,2,3,5}). now start with empty set and draw lines to 1,2,3,5.. then draw line to 1,2 from the points 1 and 2.draw line from 2 and 3 to join 2,3.then draw lines to 5 from 1,2,3... then from there draw lines to {1,2,3} from [1,2},{2,3}. then draw lines to {1,3,5} from {3,5}and {1,5} . then again draw a line to next set , and atlast draw lines from all the previous sbset to the last subset...