3
$\begingroup$

I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.

For example, suppose we have a set (1, 2, 3, 4, 5) and a number of constraints:

  • 1 should be before 2
  • 2 should be before 4
  • 4 should be before 1

(which is of course infeasible).

Is there a simple algorithm for checking the feasibility of order-constraints? (that does not rely on lp-solvers)?

I do not have anything against Lp-solving, but i suspect that simpler algorithms are available.

$\endgroup$
  • $\begingroup$ You may be interested in Contraint programming (which is not the same as linear programming, but a superset). in particular you are interested in the algorithm for constraint propagation of binary contraints. Try searching a bit these terms and you will find some notions about consistency and some general algorithms, and also some interesting special cases (e.g. propagation of the "all different" constraint, which makes use of the maximal matching problem). $\endgroup$ – Bakuriu Sep 12 '16 at 16:18
5
$\begingroup$

Yes. ​ That task is called topological sorting.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you very much, that was exactly what i wanted to know! $\endgroup$ – user3499209 Sep 12 '16 at 10:57

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.