On Tseitin Formulas, Read-Once Branching Programs and Treewidth
- 9 October 2020
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 65 (3) , 613-633
Abstract
No abstract availableKeywords
Funding Information
- Russian Science Foundation (16-11-1012)
This publication has 18 references indexed in Scilit:
- On Tseitin Formulas, Read-Once Branching Programs and Treewidth2019
- Cops-Robber Games and the Resolution of Tseitin Formulas2018
- On Small-Depth Frege Proofs for Tseitin for Grids2017
- Polynomial Bounds for the Grid-Minor TheoremJournal of the ACM, 2016
- Excluded Grid Theorem2015
- Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor SizeAlgorithmica, 2012
- Satisfiability, Branch-Width and Tseitin tautologiescomputational complexity, 2011
- Treewidth in Verification: Local vs. Global2005
- Constraint Propagation as a Proof System2004
- "Planar" tautologies hard for resolution2001