An Optimal Algorithm for Computing the Integer Closure of UTVPI Constraints

DOI10.1007/978-3-319-30139-6_13MaRDI QIDQ2803820zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• An Improved Tight Closure Algorithm for Integer Octagonal Constraints
• 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

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)