Complexity of solving a system of difference constraints with variables restricted to a finite set
Fishburn developed an algorithm to solve a system of m difference constraints whose n unknowns must take values from a set with k real numbers [Solving a system of difference constraints with variables restricted to a finite set, Inform Process Lett 82 (3) (2002) 143–144]. We provide an implementation of Fishburn's algorithm that runs in O(n+km) time.
READ FULL TEXT