Improved algorithms for optimal length resolution refutation in difference constraint systems
From MaRDI portal
Publication:1941901
DOI10.1007/s00165-011-0186-3zbMath1259.68261OpenAlexW1987170234MaRDI QIDQ1941901
Xiaofeng Gu, Matthew Williamson, K. Subramani and Vahan Mkrtchyan
Publication date: 22 March 2013
Published in: Formal Aspects of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00165-011-0186-3
algorithmgraphdifference constraint systemnegative cycle detectionoptimal length resolution refutation
Related Items (7)
Empirical analysis of algorithms for the shortest negative cost cycle problem ⋮ A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints ⋮ On the negative cost girth problem in planar networks ⋮ Randomized algorithms for finding the shortest negative cost cycle in networks ⋮ Unit read-once refutations for systems of difference constraints ⋮ On approximating optimal weight ``no-certificates in weighted difference constraint systems ⋮ Analyzing unit read-once refutations in difference constraint systems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal length resolution refutations of difference constraint systems
- The intractability of resolution
- Fourier-Motzkin elimination extension to integer programming problems
- An analysis of totally clairvoyant scheduling
- Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality
- On deciding the non‐emptiness of 2SAT polytopes with respect to First Order Queries
- Scaling Algorithms for the Shortest Paths Problem
- Automated Reasoning
- The Complexity of Propositional Proofs
- A Machine-Oriented Logic Based on the Resolution Principle
This page was built for publication: Improved algorithms for optimal length resolution refutation in difference constraint systems
