Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints

DOI10.1007/978-3-031-49614-1_28MaRDI QIDQ6606248

K. Subramani and Vahan Mkrtchyan, Piotr J. Wojciechowski

Publication date: 16 September 2024

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• Exact exponential algorithms.
• Some consequences of non-uniform conditions on uniform classes
• Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness
• Optimal length resolution refutations of difference constraint systems
• The octagon abstract domain
• Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• Finding read-once resolution refutations in systems of 2CNF clauses
• On integer closure in a system of unit two variable per inequality constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• Integer feasibility and refutations in UTVPI constraints using bit-scaling
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• Kernelization
• Frontiers of Combining Systems
• Parameterized Algorithms
• A Machine-Oriented Logic Based on the Resolution Principle

This page was built for publication: Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints