I usually do it via topological sort and wonder if there is a simpler way to generate a linear extension from partial orders without consider the graph of the relation.

  • 1
    $\begingroup$ Topological sort is essentially the same problem as what you are after. So I don't understand what you mean by "a simpler way". Are you referring to a particular algorithm for topological sorting? $\endgroup$ – Yuval Filmus Feb 23 '19 at 17:55
  • $\begingroup$ @YuvalFilmus yes an algorithm without using graph or depth first search $\endgroup$ – seteropere Feb 23 '19 at 17:56
  • $\begingroup$ DFS is one of the most basic algorithms one can think of, and it runs in linear time. I'm not sure how much simpler it can get. $\endgroup$ – Yuval Filmus Feb 23 '19 at 17:58

No, there is no simpler way. Topological sorting is exactly the problem of generate a linear extension from a partial order. There are several standard algorithms for topological sorting; they are already pretty simple, and there's no reason to expect anything simpler.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.