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

Santiago Cifuentes, Francisco J. Soulignac, Pablo Terlisky

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment