Encoding Treewidth into SAT
From MaRDI portal
Publication:3637156
DOI10.1007/978-3-642-02777-2_6zbMath1247.68259OpenAlexW1821762897MaRDI QIDQ3637156
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
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
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