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

2022/11/09 by Santiago Cifuentes, Cifuentes, Santiago, Francisco J. Soulignac +3
Computer Science · #68W05 #68W40 #Advanced Algebra and Logic #Advanced Database Systems and Queries #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2211.05259

openalex publication_date 2022/11/09 · openalex created_date 2022/11/16 · openalex updated_date 2026/07/28

Abstract

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.

Related

• Modular difference logic is hard
• Difference Constraints: An adequate Abstraction for Complexity Analysis of Imperative Programs
• Constraint Propagation as Information Maximization
• The alldifferent Constraint: A Survey
• Betweenness Parameterized Above Tight Lower Bound