Complexity of solving a system of difference constraints with variables restricted to a finite set

11/09/2022
by   Santiago Cifuentes, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset