On tseitin formulas, read-once branching programs and treewidth
type: Item
instance of: scholarly article
title: On tseitin formulas, read-once branching programs and treewidth
author: Ludmila Glinskih
author: Dmitry Itsykson
published in: Theory of Computing Systems
publication date: 2021-08-03T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 03Fxx
Mathematics Subject Classification ID: 68Txx
zbMATH DE Number: 7377746
zbMATH Keywords: Tseitin formulas
zbMATH Keywords: read-once branching program
zbMATH Keywords: treewidth
zbMATH Keywords: grid
MaRDI profile type: Publication
full work available at URL: s00224-020-10007-8
OpenAlex ID: W2954150872
cites work: Satisfiability, branch-width and Tseitin tautologies
cites work: Principles and Practice of Constraint Programming – CP 2004
cites work: Q5121904
cites work: Polynomial Bounds for the Grid-Minor Theorem
cites work: Excluded Grid Theorem
cites work: Treewidth in Verification: Local vs. Global
cites work: Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs
cites work: Cops-robber games and the resolution of Tseitin formulas
cites work: Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
cites work: On Tseitin formulas, read-once branching programs and treewidth
cites work: Improved bounds on the planar branchwidth with respect to the largest grid minor size
cites work: On OBDD-Based Algorithms and Proof Systems That Dynamically Change Order of Variables
cites work: Tree-width, path-width, and cutwidth
cites work: Q4856172
cites work: Search Problems in the Decision Tree Model
cites work: On the read-once property of branching programs and CNFs of bounded treewidth
cites work: Quickly excluding a planar graph
cites work: Graph minors. V. Excluding a planar graph
cites work: Q5593816
cites work: Hard examples for resolution
cites work: Branching Programs and Binary Decision Diagrams
DOI: 10.1007/S00224-020-10007-8
description: scientific article; zbMATH DE number 7377746