A Polynomial Time Algorithm for Read-Once Certification of Linear Infeasibility in UTVPI Constraints

No abstract is available for this paper.

• Publication year

  2019

• Venue

  Algorithmica

• Publication date

  2019-03-02

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00453-019-00554-z
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Finding read-once resolution refutations in systems of 2CNF clauses

  2018cited by this paper
• A Combinatorial Certifying Algorithm for Linear Feasibility in UTVPI Constraints

  2016cited by this paper
• Scaling Algorithms for Weighted Matching in General Graphs

  2014cited by this paper
• Improved algorithms for optimal length resolution refutation in difference constraint systems

  2011cited by this paper
• Tightened Transitive Closure of Integer Addition Constraints

  2009cited by this paper
• Optimal Length Resolution Refutations of Difference Constraint Systems

  2009cited by this paper
• Ontology-Based Reasoning Techniques for Multimedia Interpretation and Retrieval

  2008cited by this paper
• On Solving Boolean Combinations of UTVPI Constraints

  2007influential reference
• The Complexity of Propositional Proofs

  2007cited by this paper
• The Complexity of Read-Once Resolution

  2002cited by this paper
• NP-Completeness of Refutability by Literal-Once Resolution

  2001cited by this paper
• Propositional Proof Complexity: Past, Present and Future

  2001cited by this paper
• The octagon abstract domain

  2001cited by this paper
• Combinatorial optimization

  2000cited by this paper
• Minimum propositional proof length is NP-hard to linearly approximate

  1998cited by this paper
• Complexity of Finding Short Resolution Proofs

  1997cited by this paper
• Parametric Dispatching of Hard Real-Time Tasks

  1995cited by this paper
• The Complexity of Propositional Proofs

  1995cited by this paper
• Intractability of read-once resolution

  1995cited by this paper
• Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality

  1994cited by this paper
• Introduction to Algorithms

  1991cited by this paper
• Data structures for weighted matching and nearest common ancestors with linking

  1990influential reference
• Integer and Combinatorial Optimization

  1988cited by this paper
• Theory of linear and integer programming

  1986cited by this paper
• The Intractability of Resolution

  1985cited by this paper
• The Directed Subgraph Homeomorphism Problem

  1978cited by this paper
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

  1976cited by this paper
• Theorie der einfachen Ungleichungen.

  year unknowncited by this paper

• Unit refutability of horn constraint systems - certification and parallel complexity

  2025cites this paper
• On the Computational Complexities of Finding Selected Refutations of Linear Programs

  2024cites this paper
• Farkas Bounds on Horn Constraint Systems

  2024cites this paper
• Reachability in choice networks

  2023cites this paper
• Constrained read-once refutations in UTVPI constraint systems: A parallel perspective

  2023cites this paper
• Unit Read-once Refutations for Systems of Difference Constraints

  2023cites this paper
• Analyzing Read-Once Cutting Plane Proofs in Horn Systems

  2022cites this paper
• On the lengths of tree-like and Dag-like cutting plane refutations of Horn constraint systems

  2022cites this paper
• Integer Feasibility and Refutations in UTVPI Constraints Using Bit-Scaling

  2022cites this paper
• Tree-Like Unit Refutations in Horn Constraint Systems

  2021cites this paper
• Copy complexity of Horn formulas with respect to unit read-once resolution

  2021cites this paper
• Exact and Parameterized Algorithms for Read-Once Refutations in Horn Constraint Systems

  2021cites this paper
• Analyzing Unit Read-Once Refutations in Difference Constraint Systems

  2021cites this paper
• Finding read-once refutations in 2CNF formulas and variants - a parameterized perspective

  2020cites this paper
• On integer closure in a system of unit two variable per inequality constraints

  2020cites this paper
• Polynomial time algorithms for optimal length tree-like refutations of linear infeasibility in UTVPI constraints

  2020cites this paper
• On Unit Read-Once Resolutions and Copy Complexity

  2020cites this paper