Encoding Treewidth into SAT

DOI10.1007/978-3-642-02777-2_6zbMath1247.68259OpenAlexW1821762897MaRDI QIDQ3637156

Helmut Veith, Marko Samer

Publication date: 7 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02777-2_6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

A SAT Approach to Clique-Width ⋮ Computing optimal hypertree decompositions with SAT ⋮ Positive-instance driven dynamic programming for treewidth ⋮ A SAT Approach to Branchwidth ⋮ Positive-Instance Driven Dynamic Programming for Treewidth.

Uses Software

• Treewidthlib

Cites Work

• Treewidth lower bounds with brambles
• Towards an Optimal CNF Encoding of Boolean Cardinality Constraints
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Contraction and Treewidth Lower Bounds
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• Experimental and Efficient Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item