On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems
type: Item
instance of: scholarly article
title: On the parametrized complexity of Read-once refutations in UTVPI+ constraint systems
author: Yanyan Li
published in: Theoretical Computer Science
publication date: 2021-08-27T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7387689
zbMATH Keywords: unit two variable per inequality constraints
zbMATH Keywords: network flows
zbMATH Keywords: branching
zbMATH Keywords: parameterized complexity
zbMATH Keywords: strong exponential time hypothesis
zbMATH Keywords: read-once refutation
describes a project that uses: Yices
describes a project that uses: z3
MaRDI profile type: Publication
full work available at URL: j.tcs.2021.05.007
OpenAlex ID: W3179772470
cites work: Q3056948
cites work: Computational Complexity
cites work: On problems without polynomial kernels
cites work: A combinatorial algorithm for Horn programs
cites work: Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints
cites work: Formal Techniques, Modelling and Analysis of Timed and Fault-Tolerant Systems
cites work: Fast and Flexible Difference Constraint Propagation for DPLL(T)
cites work: Parameterized Algorithms
cites work: Kernelization
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: Q3138921
cites work: Parametric dispatching of hard real-time tasks
cites work: Q3002852
cites work: A multicommodity network-flow problem with side constraints on paths solved by column generation
cites work: Finding read-once resolution refutations in systems of 2CNF clauses
cites work: Restricted cutting plane proofs in Horn constraint systems
cites work: The complexity of read-once resolution
cites work: Frontiers of Combining Systems
cites work: Q4904144
cites work: Certifying algorithms
cites work: The octagon abstract domain
cites work: Q3813613
cites work: Two Variables per Linear Inequality as an Abstract Domain
cites work: Optimal length resolution refutations of difference constraint systems
cites work: A polynomial time algorithm for read-once certification of linear infeasibility in UTVPI constraints
cites work: Q4539605
cites work: Some consequences of non-uniform conditions on uniform classes
DOI: 10.1016/J.TCS.2021.05.007
description: scientific article; zbMATH DE number 7387689