An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints

DOI10.1007/978-3-319-30139-6_13zbMATH Open1475.68421OpenAlexW2495050057MaRDI QIDQ2803820FDOQ2803820

Authors: K. Subramani, Piotr Wojciechowski 

Publication date: 3 May 2016

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-30139-6_13

Recommendations

• Frontiers of Combining Systems
• A combinatorial certifying algorithm for linear feasibility in UTVPI constraints
• On solving Boolean combinations of UTVPI constraints.
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
• Integer feasibility and refutations in UTVPI constraints using bit-scaling

zbMATH Keywords

optimalclosurerelaxationUTVPI constraintsDijkstra steps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• The octagon abstract domain
• Introduction to algorithms
• Frontiers of Combining Systems
• Parametric dispatching of hard real-time tasks
• Weakly-relational shapes for numeric abstractions: Improved algorithms and proofs of correctness
• A Graphical Theorem of the Alternative for UTVPI Constraints

Cited In (7)

• Incremental closure for systems of two variables per inequality
• A Graphical Theorem of the Alternative for UTVPI Constraints
• On integer closure in a system of unit two variable per inequality constraints
• Incremental satisfiability and implication for UTVPI constraints
• A Bit-Scaling Algorithm for Integer Feasibility in UTVPI Constraints
• A certifying algorithm for lattice point feasibility in a system of UTVPI constraints
• An Improved Tight Closure Algorithm for Integer Octagonal Constraints

This page was built for publication: An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2803820)