Optimal length resolution refutations of difference constraint systems
From MaRDI portal
difference constraint systemsFourier-Motzkin eliminationminimum unsatisfiable subsetoptimal lengthresolution refutation
Recommendations
- Improved algorithms for optimal length resolution refutation in difference constraint systems
- On approximating optimal weight ``no-certificates in weighted difference constraint systems
- A fully polynomial time approximation scheme for refutations in weighted difference constraint systems
- Optimal length tree-like refutations of linear feasibility in UTVPI constraints
- scientific article; zbMATH DE number 1955763
Cites work
- A Machine-Oriented Logic Based on the Resolution Principle
- A new approach to dynamic all pairs shortest paths
- A note on two problems in connexion with graphs
- An analysis of totally clairvoyant scheduling
- An exponential separation between the parity principle and the pigeonhole principle
- Automated Reasoning
- Constraint-based scheduling: Applying constraint programming to scheduling problems.
- Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
- Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems
- Fourier-Motzkin elimination and its dual
- Fourier-Motzkin elimination extension to integer programming problems
- Frontiers of Combining Systems
- Handbook of automated reasoning. In 2 vols
- Handbook of proof theory
- scientific article; zbMATH DE number 5345853 (Why is no real title available?)
- scientific article; zbMATH DE number 4083375 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1222561 (Why is no real title available?)
- scientific article; zbMATH DE number 1223618 (Why is no real title available?)
- scientific article; zbMATH DE number 1179974 (Why is no real title available?)
- scientific article; zbMATH DE number 2079335 (Why is no real title available?)
- scientific article; zbMATH DE number 1538005 (Why is no real title available?)
- scientific article; zbMATH DE number 2090312 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Introduction to algorithms.
- Lower bounds for resolution and cutting plane proofs and monotone computations
- Network flows. Theory, algorithms, and applications.
- On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
- On Fourier's algorithm for linear arithmetic constraints
- On solving Boolean combinations of UTVPI constraints.
- On subclasses of minimal unsatisfiable formulas
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- Software reliability via run-time result-checking
- The Complexity of Propositional Proofs
- The Computational Complexity of Simultaneous Diophantine Approximation Problems
- The densest hemisphere problem
- The intractability of resolution
- The Shifting Bottleneck Procedure for Job Shop Scheduling
- Time bounded random access machines
Cited in
(22)- Empirical analysis of algorithms for the shortest negative cost cycle problem
- Randomized algorithms for finding the shortest negative cost cycle in networks
- Improved algorithms for optimal length resolution refutation in difference constraint systems
- On the parametrized complexity of read-once refutations in UTVPI+ constraint systems
- Analyzing unit read-once refutations in difference constraint systems
- On the lengths of tree-like and dag-like cutting plane refutations of Horn constraint systems. Horn constraint systems and cutting plane refutations
- Exact and parameterized algorithms for read-once refutations in Horn constraint systems
- Tree-like unit refutations in Horn constraint systems
- Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints
- A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
- A fully polynomial time approximation scheme for refutations in weighted difference constraint systems
- Analyzing read-once cutting plane proofs in Horn systems
- Integer feasibility and refutations in UTVPI constraints using bit-scaling
- Unit read-once refutations for systems of difference constraints
- Farkas Bounds on Horn Constraint Systems
- Arc-dependent networks: theoretical insights and a computational study
- Parameterized and exact-exponential algorithms for the read-once integer refutation problem in UTVPI constraints
- Unit refutability of Horn constraint systems -- certification and parallel complexity
- Optimal length cutting plane refutations of integer programs
- On approximating optimal weight ``no-certificates in weighted difference constraint systems
- Optimal length tree-like refutations of linear feasibility in UTVPI constraints
- On the negative cost girth problem in planar networks
This page was built for publication: Optimal length resolution refutations of difference constraint systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q846163)
